PPractick

The problem

A factory line records each part's grade as 0, 1 or 2 in a linked list, and the report needs all the 0s, then the 1s, then the 2s. With only three possible values there's no need for an O(n log n) sort. One option counts the values and overwrites them in a second pass. A cleaner option relinks the nodes into three separate chains (zeros, ones and twos) using dummy heads, then connects the chains, in one pass without changing any node's value. That matters when nodes carry more data than just the key.

Example: 1 -> 2 -> 2 -> 1 -> 2 -> 0 -> 2 -> 2 → 0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2.

Function signature

Node* sortZeroOneTwo(Node* head);  // values are 0, 1 or 2; returns the new head

Test cases

Input list	Output list	Explanation
1 -> 2 -> 2 -> 1 -> 2 -> 0 -> 2 -> 2	0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2
2 -> 2 -> 0 -> 1	0 -> 1 -> 2 -> 2
2 -> 1	1 -> 2	No zeros: the empty chain is skipped
0	0
(empty)	(empty)

(Confirm: only the values 0, 1 and 2 appear; nodes are relinked rather than having their values overwritten.)

How interviewers phrase it

• "Sort a linked list of 0s, 1s and 2s" (GeeksforGeeks).
• The linked-list version of the Dutch national flag problem (S.No 77).

Clarifying questions to ask

1. Can I change node values, or must I relink nodes?
2. Should the relative order of equal values be kept?
3. One pass required?

Follow-ups to expect

1. "What's the counting approach?"
2. "Why use dummy heads for the three chains?"
3. "How do you connect chains when some are empty?"
4. "Is it stable?"
5. "Complexity?"

Related questions

• Search in Linked List Medium
• Reverse a Doubly Linked List Medium
• Reverse a LinkedList [Iterative] Medium
• Reverse a LL Medium
• Detect a loop in LL Medium
• Find the starting point in LL Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in