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

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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

 
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

avatar
  Subscribe  
newest oldest most voted
Notify of
Top Coder
Guest
Top Coder

nice solution.. handles all corner cases well…

Anonymous
Guest
Anonymous

Please post more problems with solutions easy to understand