Sort linked list containing 0’s, 1’s and 2’s in single traversal

Given a linked list containing 0’s, 1’s and 2’s, sort linked list by doing single traversal of it.


 

For example,


Input:  0 -> 1 -> 2 -> 2 -> 1 -> 0 -> 0 -> 2 -> 0 -> 1 -> 1 -> 0 -> NULL

Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 2 -> NULL

 


 

Simple solution would be to count number of 0’s, 1’s and 2’s present in the linked list and traverse the linked list and put them back in correct order. The problem with this approach is that we need to do two traversals of the list which violates the problem constraints.
 

We can solve this problem in single traversal of the list. The idea is to maintain three pointers zeros, ones and twos. Then, we traverse the list from head to end and move each node to the corresponding list depending on its value. Finally, we combine all three lists at the end and fix the head pointer.

 
C++ implementation –
 

Download   Run Code

Output:

0 -> 0 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 2 -> null

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Related Post: Sort an array containing 0’s, 1’s and 2’s (Dutch national flag problem)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Top Coder
Guest
Top Coder

nice solution.. handles all corner cases well…

wpDiscuz