Sort a linked list of 0s, 1s and 2s

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Sort linked list of 0s, 1s, and 2s. Count and reconstruct, or Dutch National Flag on nodes.

Algorithm

1Count 0s, 1s, 2s. Overwrite nodes: first count0 nodes get 0, next count1 get 1, rest get 2.

Common Pitfalls

•Two passes: count then overwrite values. O(n). Alternative: maintain 3 separate lists and merge.

Sort a linked list of 0s, 1s and 2s.java

Java

// Approach: Count 0s, 1s, 2s. Overwrite list values in sorted order.
// Time: O(n) Space: O(1)
class Solution {
    // Function to sort a linked list of 0s, 1s and 2s.
    static Node segregate(Node head) {
        int zero = 0, one = 0, two = 0;
        Node curr = head;
        while (curr != null) {
            if (curr.data == 0)
                zero++;
            else if (curr.data == 1)
                one++;
            else
                two++;
            curr = curr.next;
        }

        curr = head;

        while (curr != null) {
            if (zero != 0) {
                curr.data = 0;
                zero--;
            } else if (one != 0) {
                curr.data = 1;
                one--;
            } else if (two != 0) {
                curr.data = 2;
                two--;
            }
            curr = curr.next;
        }

        return head;
    }
}

class Node {
    int data;
    Node next;

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

Was this solution helpful?