Sort a linked list of 0s, 1s and 2s
Problem
The list's values are only 0, 1 and 2. Sort it.
Example 1
Input: 1 → 2 → 2 → 1 → 2 → 0 → 2 → 2 Output: 0 → 1 → 1 → 2 → 2 → 2 → 2 → 2
Also asked as: Sort a LL of 0's, 1's and 2's
Test cases
Case 1
Input: [1,2,2,1,2,0,2,2] Expected: [0,1,1,2,2,2,2,2]
Case 2
Input: [2,1,0] Expected: [0,1,2]
Case 3
Input: [2,2] Expected: [2,2]
Case 4
Input: [0] Expected: [0]
View solutionHide solution1 approach
1. Count and overwrite
Time O(n)Space O(1)
Count 0s/1s/2s in one pass, then rewrite the node values.
function sort012List(head) { const c = [0, 0, 0]; for (let n = head; n; n = n.next) c[n.val]++; let n = head; for (let v = 0; v < 3; v++) while (c[v]-- > 0) { n.val = v; n = n.next; } return head;}To rewire pointers instead of values: build three sublists (0s, 1s, 2s) and concatenate.