Sort a Linked List which is already sorted on absolute values
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
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;
}
}
