7/26/2018 - 2:17 PM

Sort a linked list of 0s, 1s and 2s by changing links

Given a linked list of 0s, 1s and 2s, sort it.


Input : 2->1->2->1->1->2->0->1->0 Output : 0->0->1->1->1->1->2->2->2

Input : 2->1->0 Output : 0->1->2

Algo: Iterate through the linked list. Maintain 3 pointers named zero, one and two to point to current ending nodes of linked lists containing 0, 1, and 2 respectively. For every traversed node, we attach it to the end of its corresponding list. Finally we link all three lists. To avoid many null checks, we use three dummy pointers zeroD, oneD and twoD that work as dummy headers of three lists.