# Sort a Linked List which is already sorted on absolute values

#### linked list sorting algorithm data structure

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

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)

• C++
• Java

### C++


#include <bits/stdc++.h>
using namespace std;
struct Node
{
Node* next;
int data;
};
{
Node* newNode = new Node;
newNode->data = data;
}
{
while (curr != NULL)
{
if (curr->data < prev->data)
{
prev->next = curr->next;
curr = prev;
}
else
prev = curr;
curr = curr->next;
}
}
int main()
{
return 0;
}


### Java


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


### Questions

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) #### OpenGenus Foundation

The official account of OpenGenus IQ backed by GitHub, DigitalOcean and Discourse