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

Problem Statement

Given a linked list containing only 0s, 1s, and 2s, sort the linked list. The sorting should be done by changing links rather than just changing data values (though counting approach is also valid).

Example

Input: 1 -> 2 -> 2 -> 1 -> 2 -> 0 -> 2 -> 2
Output: 0 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 2

Input: 2 -> 2 -> 0 -> 1
Output: 0 -> 1 -> 2 -> 2

Brute Force Approach (Counting)

Intuition

Count the occurrences of 0s, 1s, and 2s, then overwrite the linked list with the counted values in order.

Algorithm

Traverse the list and count 0s, 1s, and 2s
Traverse again and overwrite values: first count0 zeros, then count1 ones, then count2 twos
Return the head

Code

java

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

public class Sort012Counting {
    public static Node sortListCounting(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Count 0s, 1s, and 2s
        int count0 = 0, count1 = 0, count2 = 0;
        Node temp = head;
        
        while (temp != null) {
            if (temp.data == 0) count0++;
            else if (temp.data == 1) count1++;
            else count2++;
            temp = temp.next;
        }
        
        // Overwrite values
        temp = head;
        
        while (count0 > 0) {
            temp.data = 0;
            count0--;
            temp = temp.next;
        }
        
        while (count1 > 0) {
            temp.data = 1;
            count1--;
            temp = temp.next;
        }
        
        while (count2 > 0) {
            temp.data = 2;
            count2--;
            temp = temp.next;
        }
        
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n) - Two passes through the list
Space Complexity: O(1) - Only constant extra space

Optimal Approach (Changing Links)

Intuition

Create three separate lists for 0s, 1s, and 2s. Traverse the original list once, appending each node to the appropriate list. Finally, connect the three lists together.

Algorithm

Create three dummy heads for lists of 0s, 1s, and 2s
Traverse the original list and append each node to its respective list
Connect: 0s list -> 1s list -> 2s list
Handle edge cases where any list might be empty
Return the head of the combined list

Code

java

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

public class Sort012Optimal {
    public static Node sortListOptimal(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // Create dummy nodes for three lists
        Node zeroHead = new Node(-1);
        Node oneHead = new Node(-1);
        Node twoHead = new Node(-1);
        
        Node zero = zeroHead;
        Node one = oneHead;
        Node two = twoHead;
        
        Node curr = head;
        
        // Distribute nodes to three lists
        while (curr != null) {
            if (curr.data == 0) {
                zero.next = curr;
                zero = zero.next;
            } else if (curr.data == 1) {
                one.next = curr;
                one = one.next;
            } else {
                two.next = curr;
                two = two.next;
            }
            curr = curr.next;
        }
        
        // Connect the three lists
        // 0s -> 1s -> 2s
        zero.next = (oneHead.next != null) ? oneHead.next : twoHead.next;
        one.next = twoHead.next;
        two.next = null;
        
        // New head is the first non-empty list
        Node newHead = zeroHead.next;
        if (newHead == null) newHead = oneHead.next;
        if (newHead == null) newHead = twoHead.next;
        
        return newHead;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] values = {1, 2, 2, 1, 2, 0, 2, 2};
        Node head = new Node(values[0]);
        Node curr = head;
        for (int i = 1; i < values.length; i++) {
            curr.next = new Node(values[i]);
            curr = curr.next;
        }
        
        System.out.print("Original list: ");
        printList(head);
        
        head = sortListOptimal(head);
        
        System.out.print("Sorted list: ");
        printList(head);
    }
}

Complexity Analysis

Time Complexity: O(n) - Single pass through the list
Space Complexity: O(1) - Only using constant extra space (dummy nodes)

Comparison of Approaches

| Aspect | Counting Approach | Changing Links Approach | |--------|-------------------|------------------------| | Time | O(n) - Two passes | O(n) - Single pass | | Space | O(1) | O(1) | | Data Modification | Yes (overwrites values) | No (only changes links) | | Stability | N/A (only 0,1,2) | Stable (preserves order within same value) | | Applicable When | Values can be overwritten | Links must be changed |

Key Takeaways

Two Valid Approaches: Both counting and link manipulation achieve O(n) time
Counting is Simpler: If data modification is allowed, counting is straightforward
Link Manipulation: Preferred when data shouldn't be modified or for practice
Dutch National Flag: This problem is related to the DNF algorithm for arrays
Dummy Nodes: Using dummy heads simplifies list construction and edge case handling
Connection Logic: Carefully handle empty sublists when connecting
Interview Preference: Link manipulation often preferred as it demonstrates linked list mastery

Sort a LL of 0s, 1s and 2s

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

Problem Statement

Example

Brute Force Approach (Counting)

Intuition

Algorithm

Code

Complexity Analysis

Optimal Approach (Changing Links)

Intuition

Algorithm

Code

Complexity Analysis

Comparison of Approaches

Key Takeaways