AlgoViz
HomeLinked List

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

Medium

Three chains, concatenated

Problem

Given a linked list whose node values are only 0, 1 or 2, sort it so all 0s come first, then 1s, then 2s. Return the head.

In simple words

Count how many 0s, 1s and 2s there are (or splice three chains) and rebuild in order.

The idea

Make one dummy-headed chain for each value, append each node to the chain matching its value, then join the three. It is a single pass with no value swapping, which also keeps it stable.

The trick

  • Dummy heads make the appends uniform — no empty-chain special cases.
  • Terminate the last chain with null before returning.
  • One pass; a counting pass plus overwrite also works if mutation is allowed.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
0
2
1
0
0
1
2
3
4
5

Step 1 of 2. Here's the example — head = [1, 2, 0, 2, 1, 0] Values: 1, 2, 0, 2, 1, 0.

1/2
Optimal
timeO(n)spaceO(1)
1zeroD, oneD, twoD = dummy, dummy, dummy2for node in list:3  append node to (zero/one/two) chain by value4// join: zeros -> ones -> twos5return zeroChain

Input

array
[1, 2, 0, 2, 1, 0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 2 -> 1 -> 2 -> 0 -> 2 -> 2
Output:
0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2
Explanation:
All 0s, then 1s, then 2s.

Example 2

Input:
list = 2 -> 2 -> 0 -> 1
Output:
0 -> 1 -> 2 -> 2
Explanation:
Becomes 0,1,2,2.

Example 3

Input:
list = 0
Output:
0
Explanation:
Single 0.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.