Reading time: 15 minutes | Coding time: 5 minutes

The problem at hand is to sort a singly Linked List which is already sorted on absolute value. Sorting always takes a time complexity of O(N log N) and in this case, we will be utilizing our knowledge of the data within the Linked List to sort it in O(N) time complexity.

Initial data: 5 1 -3 2 4 9 10 0 -11 -2

Data sorted on absolute value: 0 1 -2 -3 4 5 9 10 -11

Data sorted on value: -11 -3 -2 0 1 4 5 9 10

Note: The challenge is with negative numbers. As we are getting elements sorted in absolute value:

• the negative numbers will be in reverse order.
• the positive number will be in correct order.
• Negative and positive numbers will be mixed in the original Linked List.

Brute Force approach

The brute force approach is to simply sort the Linked List. We can use any of the standard sorting algorithms like Quick Sort or Merge Sort for this.

Step:

1. Sort Linked List using Quick Sort

Depending on the sorting algorithm you will choose, the complexity will be:

• Time Complexity: O(N logN)
• Space Complexity: O(1) or O(N)

Considering the information from the problem statement that the values are sorted in absolute value, we might be able to achieve better performance.

Algorithm

Key idea: Positive values are already sorted and negative values are sorted in reverse order

The steps to solve this problem are:

1. Traverse Linked List from the front to end.
2. For every negative number encountered:
   2.1. move the negative element to the front of the Linked List.
3. The modified Linked List is sorted.

This takes linear time as step 2 can be executed in constant time O(1) as we have the head node and can make the current node as the new head node easily.

Initial data: 5 1 -3 2 4 9 10 0 -11 -2

Data sorted on absolute value: 0 1 -2 -3 4 5 9 10 -11

Positive values separated in order: 0 1 4 5 9 10

Negative values separated in order: -2 -3 -11

Hence, negative values are sorted in reverse order

We can perform delete() and append() operations in a Linked List in O(1) time.

So the key idea is to traverse the Linked List from the front to the end and delete a node with a negative value and append it to the front of the Linked List.

The pseudocode is as follows:

Node prev = head; // NODE 1
Node curr = head.next; // NODE 2

while(curr != null) // END OF LINKED LIST
{
    // This happens when NODE 2 (curr) has negative element.
    // Note negative elements are sorted in absolute value.
    if(curr.data < prev.data)
    {
        // Move curr (NODE 2) to front
        prev.next = curr.next;
        curr.next = head;
        head = curr;
        // Update NODE1 and NODE2
        curr = prev;
    }
    else
    {
        // Update NODE1 and NODE2
        prev = curr;
        curr = curr.next;
    }
}

Example

Initial data: 5 1 -3 2 4 9 10 0 -11 -2

Data sorted on absolute value: 0 1 -2 -3 4 5 9 10 -11

Taverse it from the front and stop when a negative value is encountered

Negative value found: -2 : Delete the node and append it to the front

Data currently: -2 0 1 -3 4 5 9 10 -11

Negative value found: -3 : Delete the node and append it to the front

Data currently: -3 -2 0 1 4 5 9 10 -11

Negative value found: -11 : Delete the node and append it to the front

Data currently: -11 -3 -2 0 1 4 5 9 10

End of Linked List encountered

Data is sorted

Sorted data: -11 -3 -2 0 1 4 5 9 10

Complexity

• Worst case time complexity: Θ(N)
• Average case time complexity: Θ(N)
• Best case time complexity: Θ(N)
• Space complexity: Θ(1)

Implementations

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    Node* next;
    int data;
};
void push(Node** head, int data)
{
    Node* newNode = new Node;
    newNode->next = (*head);
    newNode->data = data;
    (*head) = newNode;
}
void sortList(Node** head)
{
    Node* prev = (*head);
    Node* curr = (*head)->next;
    while (curr != NULL)
    {
        if (curr->data < prev->data)
        {
            prev->next = curr->next;
            curr->next = (*head);
            (*head) = curr;
            curr = prev;
        }
        else
            prev = curr;
        curr = curr->next;
    }
}
int main()
{
    Node* head = NULL;
    push(&head, 1);
    push(&head, -2);
    push(&head, -3);
    push(&head, 4);
    sortList(&head);
    return 0;
}

Implementation in Java:

class Sort_Linked_List
{
    static Node head;     
    static class Node
    {
        int data;
        Node next;
        Node(int d) 
        {
            data = d; 
            next = null; 
        }
    }
    Node sortedList(Node head)
    {
        Node prev = head;
        Node curr = head.next;
        while(curr != null)
        {
            if(curr.data < prev.data)
            {
                prev.next = curr.next;
                curr.next = head;
                head = curr;
                curr = prev;
            }
            else
            prev = curr;
            curr = curr.next;
        }
        return head;
    }
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
} 

Questions