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; single pass preferred for the node-rearranging variant.

Example

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

Expected approach

• Two accepted solutions: (1) counting — one pass to count 0s/1s/2s, second pass overwriting values; simple but mutates values. (2) Pointer rearrangement — maintain three sublists (heads/tails for 0s, 1s, 2s), append each node to its bucket, then stitch the lists; preserves node identity, one pass, O(1) space. Be ready to explain when overwriting values is unacceptable (e.g. nodes carry other payload).