Absolute sorting on a single linked list
Given a singly linked list which is ordered in terms of absolute value. Return the sorted linked list in ascending order (based on their original values). No additional storage should be used.
Example:
Given the linked list: 1->2-> -3->4-> -5->NULL
After ordering based on original values output will be:
-5 -> -3 -> 1 ->2->4->NULL
Given the linked list: 1->2->3->4->5->6->NULL
After ordering based on original values output will be:
1->2->3->4->5->6->NULL
The problem can be solved using the following concept:
So the basic algorithm is:
1. Constructing list1 & list2 out of list
This can be done by traversing the list and checking node values. If the current node is a non-negative node, append it to the list1 else append it to the list2.
2. Reverse the list2 //If list2 is constructed then only
So the list has been split to list1 and list2 ( store1 and store2 be their respective heads),
Now, we need to reverse the list2. It's pretty much similar as we did in reverse a single linked list.
Pre-requisites:
3. Appending list1 to reversed list2 //if list2 exists
Traverse list1 and append list2 at the end.
Example with explanation:
C++ implementation:
Output