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

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

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

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?