Given a linked list with nodes as 0s,1s and 2s, sort the linked list: all nodes with 0s come first, then 1s and at last 2s. For example:
List : 0->1->1->0->2->2->1->2->NULL Output : 0-.0->1->1->1->2->2->2->NULL
First method is to count number of nodes with each value, like how many nodes with data as 0, 1 and 2. Once we know count of each value, start with lowest node value 0 let’s there are n such nodes, create n nodes with value 0. Then check number of nodes with values 1 (say m) and then create m such nodes and out at the end of list which was created with value 0. Similarly with count and value 2.
In above approach, we create new nodes which takes extra space. We can avoid wasting space by using the same nodes of list. Approach will be same as above, only difference will be that original nodes of list will be used and no new node will be created.
Algorithm to sort a list with 0s,1s and 2s
1. Traverse original list and count number of nodes with value 0 (n1), 1 (n2) and 2 (n3) 2. Now traverse list again, fill first n1 nodes with 0, next n2 nodes with 1 and last n3 nodes with 2.
Complexity of both methods above is O(n).
Some purists will say that we should not modify the content of original nodes of list. At the same time extra space should not be used and we have to solve the problem of sorting a list of 0,1 and 2.
To achieve our goal with above given constraints, only way is to re-arrange nodes of lists. This is simple thing to do as we have only three different values. Algorithm is given below and commonly know as Dutch flag algorithm:
- when you encounter 0 move it to the start - when you encounter 2 move it to the end. - when you encounter 1 , simply skip it .
Code for above algorithm to sort a list with 0s,1s and 2s
Complexity of above algorithm is O(n) and space complexity is O(1).
Input: 1->1->2->2->1->2->NULL Output: 1->1->1->2->2->2->NULL Input: 0->1->0->1->2->1->2->NULL Output : 0->0->1->1->1->2->2->NULL
Please share if you see something wrong or any other suggestion. Sharing is caring.