Last Updated: 6 Jan, 2021
Sort linked list of 0s 1s 2s
Easy
Asked in companies
Given a linked list of 'N' nodes, where each node has an integer value that can be 0, 1, or 2. You need to sort the linked list in non-decreasing order and the return the head of the sorted list.
Example:
Given linked list is 1 -> 0 -> 2 -> 1 -> 2.
The sorted list for the given linked list will be 0 -> 1 -> 1 -> 2 -> 2.
Input Format :
The first line contains an integer 'N', the size of the linked list.
The second line contains 'N' space-separated integers containing 0, 1 and 2 only.
Output Format :
The output contains all the integers in non-decreasing order.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
The approach would be counting the number of occurrences of 0, 1, and 2. Then updating the data of the linked list in sorted order.
- Make 3 different variables to store the count of 0, 1 and 2.
- Traverse over the given linked list and increase the count of respective variables.
- Now traverse the linked list again and update data of first count(0) number of nodes to 0, then next count(1) number of nodes to 1 and the remaining count(2) number of nodes to 2.
The simple approach would be separating the given linked list into 3 linked lists having 0s, 1s and 2s. Then reconnecting them in sorted fashion.
- Take 3 pointers to store separated linked lists.
- Traverse the given linked list, unlink current node from the linked list and append it to its respective linked list pointer.
- Connect the 3 linked lists in order 0 then 1 and then 2 to get the sorted linked list.