Sort a Linked List of 0s, 1s and 2s — Problem & Solution
Sort a Linked List of 0s, 1s and 2s solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sort a Linked List of 0s, 1s and 2s is an easy coding problem on sorting and counting, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Sorting, Counting
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a singly linked list in which every node holds 0, 1 or 2. Rearrange it so that all the 0s come first, then all the 1s, then all the 2s, and return the head of the sorted list.
Example 1
Input: head = [1,2,2,1,2,0,2,2]
Output: [0,1,1,2,2,2,2,2]
Example 2
Input: head = [2,2,0,1]
Output: [0,1,2,2]
Example 3
Input: head = [1]
Output: [1]
Constraints
1 <= number of nodes <= 10^6Node.val is 0, 1 or 2
Hints for Sort a Linked List of 0s, 1s and 2s
Hint 1
There are only three possible values — a general sort is more than you need.
Hint 2
Count how many 0s, 1s and 2s the list holds in one pass.
Hint 3
In a second pass, overwrite the values: the first
c0nodes get 0, the nextc1get 1, the rest 2. (Relinking nodes into three chains works too.)
How to solve Sort a Linked List of 0s, 1s and 2s
With only three distinct values, the sorted list is fully determined by how many of each there are. Count them, then write the values back in order.
Approach
- Walk the list and count
c0,c1,c2. - Walk it again: write 0 into the first
c0nodes, 1 into the nextc1, 2 into the rest. - Return
head.
Why it works
The sorted sequence of the values is c0 zeros, c1 ones and c2 twos, and the list has exactly c0 + c1 + c2 nodes, so overwriting them in that order produces the sorted list.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- If the nodes carry more than the value (data you must keep with it), overwrite is not allowed — instead relink the nodes into three chains (zeros, ones, twos) and join them, taking care with empty chains.
- A comparison sort on a linked list costs O(n log n) and is easy to get wrong.
Reference solution
Python
from typing import Optional
def segregate(head: Optional[ListNode]) -> Optional[ListNode]:
count = [0, 0, 0]
node = head
while node:
count[node.val] += 1
node = node.next
node, value = head, 0
while node:
while count[value] == 0:
value += 1
node.val = value
count[value] -= 1
node = node.next
return headJava
public static ListNode segregate(ListNode head) {
int[] count = new int[3];
for (ListNode node = head; node != null; node = node.next) count[node.val]++;
int value = 0;
for (ListNode node = head; node != null; node = node.next) {
while (count[value] == 0) value++;
node.val = value;
count[value]--;
}
return head;
}C++
ListNode* segregate(ListNode* head) {
int count[3] = {0, 0, 0};
for (ListNode* node = head; node; node = node->next) count[node->val]++;
int value = 0;
for (ListNode* node = head; node; node = node->next) {
while (count[value] == 0) value++;
node->val = value;
count[value]--;
}
return head;
}JavaScript
var segregate = function(head) {
var count = [0, 0, 0];
for (var node = head; node !== null; node = node.next) count[node.val]++;
var value = 0;
for (node = head; node !== null; node = node.next) {
while (count[value] === 0) value++;
node.val = value;
count[value]--;
}
return head;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 274 sorting problems · the whole catalogue
Learn the technique: Sorting Algorithms