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

You are given the head of a singly linked list whose every node holds one of just three values — 0, 1, or 2. Rearrange the list in place so that all the 0s come first, then all the 1s, and finally all the 2s. Return the head of the rearranged list.

The relative order among equal values does not matter — only that the three groups end up in the order 0s, then 1s, then 2s.

Hints

· Stuck? Reveal one nudge at a time.

The values come from an extremely small, fixed set — do you actually need to compare any two of them?

You could count how many 0s, 1s, and 2s exist, then rewrite the list from those counts.

To avoid touching node data at all, split the nodes into three separate chains by value and join them 0s → 1s → 2s.

Common doubts

No. Only the group order (all 0s, then 1s, then 2s) is required; ties can appear in any order. Both the counting and relinking approaches are fine.

It is a valid and common approach and gives O(n) time. The relinking approach is preferred when the nodes carry a payload you must not overwrite, or when the interviewer forbids mutating values.

A comparison sort is O(n log n). Because the values are limited to 0, 1, 2, you can sort in O(n) — comparisons add no information when a 0 always precedes a 1 precedes a 2.

Interview follow-ups

· What an interviewer asks next.

Generalize counting sort: use a size-k tally, or k buckets of relinked sublists concatenated in key order — still O(n) when k is small and known.

It is the linked-list cousin. On an array you can do a single-pass three-pointer partition in place; on a list, relinking into three chains achieves the same one-pass O(1)-space result.

Fun facts

Sorting three values without comparisons is the linked-list twin of Dijkstra's 'Dutch National Flag' problem, named for its three horizontal stripes.
The count-and-rewrite trick is just counting sort — the same linear-time idea behind radix sort used to order huge integer and string datasets.

Asked at

AmazonMicrosoftAdobeFlipkartGoogle

Frequently Sometimes Occasionally

Example 1

Input: head = [1, 2, 2, 1, 2, 0, 2, 2]
Output: [0, 1, 1, 2, 2, 2, 2, 2]
Every 0 is pulled to the front, every 2 pushed to the back, and the 1s settle in between.

Example 2

Input: head = [2, 2, 0, 1]
Output: [0, 1, 2, 2]
The single 0 leads, the 1 follows, and both 2s trail at the end.

Constraints

- 1 <= number of nodes <= 10^6 - 0 <= node value <= 2

A list of only three distinct values is a special gift: you never have to compare anything. Let's go from the obvious sort to a single-pass rewire that touches each node exactly once.

Prerequisites

Before you start

· Concepts used directly in the solution.

Linked list traversal. Walking a list with a moving pointer until it falls off the end at null.

Counting sort idea. When values come from a tiny fixed set, you can sort by tallying counts instead of comparing pairs.

Pointer relinking. Rebuilding order by rewiring next pointers rather than copying node data.

Understand the problem

In plain words: the values 0, 1, 2 are their own sort keys. Formally, partition the nodes into three groups by value and concatenate them in the order 0-group, 1-group, 2-group.

Worked example — head = 1 → 2 → 2 → 1 → 2 → 0 → 2 → 2

bucket 0:  0
bucket 1:  1 → 1
bucket 2:  2 → 2 → 2 → 2 → 2

glue in order 0,1,2:
  0 → 1 → 1 → 2 → 2 → 2 → 2 → 2

Clarifying questions

Asking two sharp questions before coding shows you read the guarantees instead of assuming them — that is what separates a senior candidate from someone who dives straight in.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are the values strictly limited to 0, 1, and 2?”

If a stray 3 can appear, counting into three buckets silently drops it — I would need a general sort instead.

Edge cases

“Can the list be a single node, or already sorted?”

Both must pass untouched; the relinking must not create a cycle or lose the tail.

Constraints and scale

“How large can the list get?”

At 10^6 nodes an O(n log n) comparison sort is wasteful — the three-value structure lets me do a single O(n) pass.

The ideal opening — say it like this

Before I code, let me confirm the guarantees.

First — are the node values always exactly 0, 1, or 2, with nothing else possible?

And finally — a single node or an already-sorted list should return unchanged, correct?

Key observations

1Aha

With three fixed values, counting beats comparing

A comparison sort asks "is a before b?" over and over. But here the answer is free: a 0 always precedes a 1 which always precedes a 2. So you can just count how many of each you have and lay them down in order — no comparisons at all.

2Aha

You do not have to move data — you can move pointers

Instead of overwriting each node's value, keep three growing sublists and append each node to the one matching its value. This never touches the payload, which matters when nodes carry more than an integer.

zero:  0-dummy → …0 nodes…
one:   1-dummy → …1 nodes…
two:   2-dummy → …2 nodes…
stitch:  zero-tail → one-head → two-head

3Aha

One clean pass is enough

The pointer method visits each node once, deciding its bucket on the spot. Counting needs two passes (tally, then rewrite). Both are O(n), but the single-pass rewire is the tightest and never mutates data.

Brute force vs optimal

	Collect & sort	Count & rewrite	Three lists (relink)
Time	O(n log n)	O(n)	O(n)
Space	O(n)	O(1)	O(1)
Passes	2	2	1
Mutates data

The full code for each approach lives in the Approaches selector below.

Summary

Key takeaway

When the universe of values is tiny and fixed, throw away comparisons: bucket by value and concatenate. On a linked list you can bucket by relinking, giving an O(n) time, O(1) space, single-pass, data-preserving sort.

zeroTail, oneTail, twoTail ← three dummy heads
for each node in list:
    append node to the tail matching node.value
stitch: zeroTail → oneHead → twoHead → null
return zeroDummy.next