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

Easy
1995.

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

Sort a Linked List of 0s, 1s and 2s is an easy coding problem on sorting and counting, asked in Amazon and Microsoft interviews.

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^6
  • Node.val is 0, 1 or 2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var segregate = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^6
  • Node.val is 0, 1 or 2

Hints for Sort a Linked List of 0s, 1s and 2s

  1. Hint 1

    There are only three possible values — a general sort is more than you need.

  2. Hint 2

    Count how many 0s, 1s and 2s the list holds in one pass.

  3. Hint 3

    In a second pass, overwrite the values: the first c0 nodes get 0, the next c1 get 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

  1. Walk the list and count c0, c1, c2.
  2. Walk it again: write 0 into the first c0 nodes, 1 into the next c1, 2 into the rest.
  3. 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 head

Java

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