Sort Linked List

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
MakeMyTripMicrosoftRed Hat

Problem statement

You are given a linked list of 'N' nodes where nodes can contain values 0, 1, and 2 only. Your task is to sort the linked list.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains 'N'(number of nodes in the linked list) space-separated integers representing the value of each node. -1 at the end denotes NULL pointer.

For example : 
The input 0 1 2 -1 denotes a linked list containing 3 nodes represented as:

Output format : 
For each test case, in a separate line, print the final sorted linked list.
Note : 
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 100000
0 <= data <= 2

 where ‘T’ is the total number of test cases, 'N' is the total number of nodes in the linked list and ‘data’ is the value of any node of the linked list.
Sample Input 1 :
2
0 1 1 2 2 1 1 1 0 1 -1
2 2 2 1 0 -1
Sample Output 1 :
0 0 1 1 1 1 1 1 2 2 
0 1 2 2 2
Explanation of The Sample Input 1 :
For the first test case :
The given linked list is :
0 -> 1 ->  1 ->  2 -> 2 -> 1 -> 1 -> 1 -> 0 -> 1 -> null

Therefore after sorting the list will become :
0 -> 0 ->  1 ->  1 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> null

For the second test case :
The given linked list is :
2 -> 2 ->  2 ->  1 -> 0 -> null

Therefore after sorting the list will become-
0 -> 1 ->  2 ->  2 -> 2 -> null
Sample Input 2 :
3
0 0 0 -1
0 1 1 2 2 -1
2 2 2 2 2 0 -1
Sample Output 2 :
0 0 0
0 1 1 2 2 
0 2 2 2 2 2
Hint

Can you sort the list by counting?

Approaches (2)
By - counting

The idea is to count the number of zero’s, one’s and two’s and then iterate through the list again from beginning to end and put zero’s, then one’s and then two’s.

  • Declare three variables countZero, countOne and countTwo to store the count of 0, 1 and 2 respectively. Initialize them with zero.
  • Run a loop till the head of the linked list reaches NULL.
    • If the data of node is zero increment countZero by one
    • Similarly increment counts for ones and twos with respective conditions.
  • After this loop, again iterate through the linked list:
    • Update countZero number of zeros.
    • Update countOne number of one’s.
    • Update countTwo number of two’s. and first put all the zero’es that are countZero and then put ones and finally put twos in the end.
  • Return head of the linked list.
Time Complexity

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

 

We are iterating the linked list once for counting and after that for updating the values in the linked list that takes O(N) time. So, the overall Time Complexity becomes O(N).

Space Complexity

O(1).

 

We are using constant extra space. Hence, the overall Space Complexity is O(1).

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