Sort a Linked List which is already sorted on absolute values

Algorithm
Example
Complexity
Implementations
Questions

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

Algorithm


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


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.

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


  • C++
  • Java

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;
}

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

What is the space complexity of this algorithm?

O(1)
O(N)
O(N log N)
O(N^2)

What is the time complexity of this algorithm in case of doubly circular linked list?

O(N)
O(1)
O(N log N)
O(N^2)