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