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

You are given the head of a singly linked list where every node value is 0, 1, or 2. Sort the list so all 0s come first, then all 1s, then all 2s, and return…

You are given the head of a singly linked list where every node value is 0, 1, or 2. Sort the list so all 0s come first, then all 1s, then all 2s, and return the head of the sorted list. The examples show node values in head-to-tail order. Solve it in `O(n)` time and `O(1)` extra space. For example, `[1, 2, 0, 1, 2, 0, 1]` is 1 → 2 → 0 → 1 → 2 → 0 → 1; sorted it becomes `[0, 0, 1, 1, 1, 2, 2]`. For `[2, 0, 2, 0]` (no 1s) the result is `[0, 0, 2, 2]`.

- `1 <= nodes.length <= 10^5` - Each `nodes[i]` is exactly `0`, `1`, or `2`. - The list is a proper singly linked list with no cycles.

Example 1: input nodes = [1,2,0,1,2,0,1]; output [0,0,1,1,1,2,2]. Two 0s, three 1s, two 2s — grouped 0s, then 1s, then 2s.

Example 2: input nodes = [2,0,2,0]; output [0,0,2,2]. Two 0s and two 2s, no 1s. The 0s come first, then the 2s.

Example 3: input nodes = [0]; output [0]. A single node is already sorted.

Category: Linked List. Topic: linked-list. Difficulty: Medium. Patterns: linked-list-traversal.