Sort a linked list of 0s, 1s and 2s

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.