Sort Linked List of 0s, 1s and 2s

Problem Given a singly linked list whose node values are only 0, 1, or 2, sort it in place (Dutch national flag on a linked list).

Input / Output

• Input: head of the linked list.
• Output: head of the sorted list (all 0s, then 1s, then 2s).

Constraints

• Up to 10^5 nodes; O(n) time, O(1) extra space; a single pass is preferred for the node-rearranging variant.

Example

• 1→2→0→1→2→0 → 0→0→1→1→2→2