Sort Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
39 upvotes
Asked in companies
AdobeAmazonTech Mahindra

Problem statement

You are given a Singly Linked List of integers which is sorted based on absolute value.

You have to sort the Linked List based on actual values.

The absolute value of a real number x, denoted |x|, is the non-negative value of x without regard to its sign.

Example:
If the given list is {1 -> -2 -> 3} (which is sorted on absolute value), the returned list should be {-2 -> 1 -> 3}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains a single integer ‘T’, representing the number of test cases or queries to be run. Then the T test cases follow.

The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

It is guaranteed that the given list is sorted based on absolute value.
Output Format:
For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1.

The output of each test case is printed in a separate line.
Note :
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= 'N' <= 5 * 10^4
-10^9 <= 'data' <= 10^9 and 'data' != -1

Where 'N' denotes the number of elements in the Singly Linked List and 'data' represents the value of those elements.

Time Limit : 1 sec
Sample Input 1:
3
1 -2 3 -1
9 9 -1
4 -1
Sample Output 1:
-2 1 3 -1
9 9 -1
4 -1
Explanation for Sample Input 1:
For the first test case:
On arranging element from lowest to highest we get ‘-2 1 3 -1’ so we return it as the answer.


For the second test case:
On arranging element from lowest to highest we get ‘9 9 -1’ so we return it as the answer.


For the third test case:
On arranging element from lowest to highest we get ‘4 -1’ so we return it as the answer.
Sample Input 2:
2
1 1 1 -1
3 -3 -1
Sample Output 2:
1 1 1 -1
-3 3 -1
Hint

You can use any sorting algorithm to sort the linked list.

Approaches (3)
Insertion Sort

We will use the ‘Insertion Sort’ algorithm to sort the given linked list.

 

Algorithm:

 

We will make a list ‘SORTED_LIST’ which is initially empty and it stores the list after sorting.

We will traverse the given list and insert the node in the ‘SORTED_LIST’ such that nodes are present in sorted order.

 

For each node follow these steps:

 

  • If ‘SORTED_LIST’ is empty or the head of the ‘SORTED_LIST’ has a value greater than the node, in this case, the current node will become the new head of ‘SORTED_LIST’.
  • Else, we will traverse the ‘SORTED_LIST’ until we find the node that has a value greater than the current node or until we reach the end.
  • We will insert the node at this position and change it’s ‘next’ value such that it points to the node which is greater than the current node.
Time Complexity

O(N ^ 2), where ‘N’ is the number of nodes in the linked list.

 

In the worst case, it takes O(N) time to insert the node in ‘SORTED_LIST’, and traversing the list takes O(N) time. Thus, the final time complexity is O(N ^ 2).

Space Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

As O(N) additional space is required to store the ‘SORTED_LIST’.

Code Solution
(100% EXP penalty)
Sort Linked List
Full screen
Console