# 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

Output:

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

## Java

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).

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 🙂