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

Sorting a linked list containing only $0\text{s}$, $1\text{s}$, and $2\text{s}$ is a classic interview problem. The objective is to rearrange the nodes in-place or via data replacement such that all $0\text{s}$ appear first, followed by all $1\text{s}$, and finally all $2\text{s}$, and then return the updated head of the linked list.

1. Why Do We Need This? (Problem Statement & Status Quo)

When dealing with arrays or primitive lists, sorting is often straightforward using standard sorting algorithms like Quicksort or Mergesort, which typically run in $O(N \log N)$ time. However, linked lists present unique constraints:

• No Random Access: Unlike arrays where you can jump to index $i$ in $O(1)$ time, linked lists require sequential traversal ($O(N)$).
• Pointer Manipulation: Sorting a linked list efficiently requires manipulating node references (pointers) rather than shifting values back and forth.
• Interviewer Constraints: Interviewers frequently push candidates past brute-force solutions to achieve optimal time and space complexities, specifically targeting a single-pass ($O(N)$ time, $O(1)$ space) pointer rearrangement approach.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Sorting Mail by Priority Bags

Imagine you are working in a mail room, and you receive an unsorted stream of letters labeled with priority codes: 0 (Express), 1 (Standard), and 2 (Bulk).

• The Naive Approach (Data Replacement): You open every single letter, write down how many Express, Standard, and Bulk letters you received on a notepad, shred the contents, and then write the correct labels back onto the envelopes in order. This requires inspecting every letter twice (once to count, once to rewrite).
• The Optimal Approach (Pointer Segregation): You set up three separate sorting bins on your desk: a 0-bin, a 1-bin, and a 2-bin. As you inspect each incoming letter once, you immediately drop it into its respective bin. At the end, you simply snap the tail of the 0-bin to the head of the 1-bin, and the tail of the 1-bin to the head of the 2-bin. You never rewrite any data; you just reroute the paths.

3. Approach 1: The Naive Two-Pass Solution (Data Replacement)

The most intuitive brute-force strategy is to count the frequency of each number ($0$, $1$, and $2$) during a first pass, and then overwrite the node data with the correct sorted sequence during a second pass.

Step-by-Step Evolution

1. First Pass (Counting): Initialize three counters (count0, count1, count2) to zero. Traverse the linked list from head to null, incrementing the corresponding counter based on the node's data value.
2. Second Pass (Overwriting): Reset a temporary pointer back to the head. Iterate through the list again, replacing node data sequentially: fill with 0s until count0 is exhausted, then fill with 1s until count1 is exhausted, and finally fill with 2s until count2 is exhausted.

Pseudocode for Naive Approach

public Node sortListTwoPass(Node head) {
    int count0 = 0, count1 = 0, count2 = 0;
    Node temp = head;
    
    // First Pass: Count frequencies
    while (temp != null) {
        if (temp.data == 0) count0++;
        else if (temp.data == 1) count1++;
        else count2++;
        temp = temp.next;
    }
    
    // Second Pass: Overwrite node data
    temp = head;
    while (temp != null) {
        if (count0 > 0) {
            temp.data = 0;
            count0--;
        } else if (count1 > 0) {
            temp.data = 1;
            count1--;
        } else {
            temp.data = 2;
            count2--;
        }
        temp = temp.next;
    }
    return head;
}

4. Why the Naive Approach Falls Short in Interviews

While the two-pass data replacement solution works correctly, it has critical drawbacks:

• Data Mutation: Overwriting data inside nodes can be problematic if the linked list nodes contain larger, complex payloads (e.g., objects containing IDs, timestamps, and metadata) alongside the sort key.
• Multiple Passes: It requires traversing the list twice ($O(2N)$ time complexity).
• Interviewer Expectations: Interviewers will immediately challenge you: "Can you solve this in a single pass without modifying the node data?" This forces the transition to the optimal pointer-segregation approach.

5. Approach 2: Optimal One-Pass Solution (Pointer Manipulation)

To achieve a single-pass solution with $O(1)$ extra space, we must segregate the nodes into three separate sub-lists (one for $0\text{s}$, one for $1\text{s}$, and one for $2\text{s}$) while traversing the original list once, and then connect them together.

The Dummy Node Strategy

To prevent null-pointer exceptions and handle empty sub-lists gracefully, we initialize three dummy nodes (initialized with a placeholder value like -1):

• zeroHead: Start of the $0$ sub-list.
• oneHead: Start of the $1$ sub-list.
• twoHead: Start of the $2$ sub-list.

We also maintain three traversal pointers (zero, one, two) initialized to point to their respective dummy heads. As we traverse the original list using a temp pointer, we attach each node directly to the tail of the appropriate sub-list and advance that sub-list's pointer.

6. Step-by-Step Flow Walkthrough

Let's trace how nodes are linked during traversal:

Once the traversal completes, we stitch the three sub-lists together:

1. Connect the tail of the $0$-list to the head of the $1$-list (or $2$-list if $1\text{s}$ are missing).
2. Connect the tail of the $1$-list to the head of the $2$-list.
3. Terminate the tail of the $2$-list with null.

7. Complete Optimized Java Implementation

Below is the complete, production-grade implementation of the optimal one-pass pointer-manipulation approach:

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Solution {
    public static Node sortList(Node head) {
        // Edge Case: Empty list or single-element list
        if (head == null || head.next == null) {
            return head;
        }

        // Initialize dummy heads for 0s, 1s, and 2s lists
        Node zeroHead = new Node(-1);
        Node oneHead = new Node(-1);
        Node twoHead = new Node(-1);

        // Pointers to track the tails of the three sub-lists
        Node zero = zeroHead;
        Node one = oneHead;
        Node two = twoHead;

        Node temp = head;

        // Single pass traversal to segregate nodes
        while (temp != null) {
            if (temp.data == 0) {
                zero.next = temp;
                zero = zero.next;
            } else if (temp.data == 1) {
                one.next = temp;
                one = one.next;
            } else {
                two.next = temp;
                two = two.next;
            }
            temp = temp.next;
        }

        // Connecting the sub-lists together
        // 1. Connect zero tail to one head (if ones exist, else connect to two head)
        zero.next = (oneHead.next != null) ? oneHead.next : twoHead.next;

        // 2. Connect one tail to two head
        one.next = twoHead.next;

        // 3. Terminate the two tail with null
        two.next = null;

        // The new head is the node following zeroHead
        Node newHead = zeroHead.next;

        return newHead;
    }
}

8. Real-World Practical Pitfalls & Edge Cases

When implementing this algorithm in languages like C++, C, or Java, be mindful of these production edge cases:

• Empty or Single-Node Lists: If head == null or head.next == null, attempting to sort is unnecessary. Always guard against this at the start to avoid null pointer exceptions.
• Missing Categories: What if the linked list contains only $0\text{s}$ and $2\text{s}$, with zero $1\text{s}$?
  • The conditional check zero.next = (oneHead.next != null) ? oneHead.next : twoHead.next; correctly bypasses the empty $1$-list and connects the tail of $0\text{s}$ directly to the head of $2\text{s}$.
• Memory Management (C++): In languages with manual memory management (like C++), remember to delete or free the temporary dummy nodes (zeroHead, oneHead, twoHead) before returning to prevent memory leaks.

9. Comparative Synthesis of Approaches

10. Summary and Key Takeaways

• Problem Goal: Rearrange a linked list containing only $0\text{s}$, $1\text{s}$, and $2\text{s}$ into sorted order by data value.
• Limitation of Brute Force: Counting elements and rewriting node data requires two passes and modifies underlying payload data.
• The Optimal Solution: Use three dummy heads (zeroHead, oneHead, twoHead) to segregate nodes during a single traversal.
• Pointer Stitching Logic: Connect the tail of the $0$-sub-list to the $1$-sub-list (or $2$-sub-list if $1\text{s}$ are absent), and the $1$-sub-list to the $2$-sub-list.
• Complexity Achievement: Accomplishes sorting in $O(N)$ time and $O(1)$ auxiliary space without creating new nodes or altering node payloads.