Last Updated: 4 Feb, 2021
Sort Linked List
Moderate
Asked in companies
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.
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.
Approaches
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.
The idea is to traverse the linked list and maintain three pointers, say zeroPointer, onePointer and twoPointer for each of the values in the linked list that are zeros, one’s and two's. Basically we will just change the links of zeros, one’s and two's.
- The idea is to maintain 3 separate linked lists.
- First for all the 1’s.
- Second for all the 2’s.
- Third for all the 3’s.
- Run a while loop till the head of the list reaches null.
- Check if the value of node is zero attach it to zero pointer.
- If the node value is one attach it to one pointer and if it is two attach it to twos pointer.
- At the end attach all three lists that is ones to zeros and twos to ones and finally return the updated head.