Sort a Linked List with 0s 1s and 2s

We have a linked list, such that nodes can contain values 0s, 1s, and 2s only.

Example

0 -> 1 -> 2 -> 2 -> 1-> 0 -> 1 -> NULL

Our task is that sort the linked list such that all 2s come after 1s and all 1s come after 0s.

We have to segregate 0s, 1s, and 2s linked list such that all nodes with 0s come to the head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.

Input : 0 -> 1 -> 2 -> 2 -> 1 -> 0 -> 1 -> NULL

Output : 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL

Approach

If we have the count of total 0s,1s and 2s in the linked list, then we can update the values of nodes to obtain the required order.

Approach simple breakdowns into three simple steps:

1. Count the total number of 0s, 1s and 2s present in the linked list.
2. Traverse the linked list again and update the values according to the order we want i.e. first place all 0s then 1s and then 2s.
3. Return the head of linked list

Complexity

• Time Complexity : O(n), n is the total number of nodes in the linked list.
• Space Complexity : O(1)

Code

# Java Code

import java.util.*;

public class SortLinkedList {

    static class Node {
        int data;
        Node next;

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

    // Method to insert a new node at the end of the linked list
    static Node insert(Node head, int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
        } else {
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }
        return head;
    }

    // Method to print the linked list
    static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Method to sort the linked list using counting sort
    static void sortLinkedList(Node head) {
        int[] count = new int[3]; // Assuming the range of data is 0 to 2

        Node current = head;
        while (current != null) {
            count[current.data]++;
            current = current.next;
        }

        current = head;
        int i = 0;
        while (current != null) {
            if (count[i] == 0) {
                i++;
            } else {
                current.data = i;
                count[i]--;
                current = current.next;
            }
        }
    }

    public static void main(String[] args) {
        Node head = null;

        // Inserting elements into the linked list
        int[] elements = {0, 1, 2, 2, 1, 0, 1};
        for (int element : elements) {
            head = insert(head, element);
        }

        System.out.println("Linked List before Sorting: ");
        printList(head);

        sortLinkedList(head);

        System.out.println("Linked List after Sorting: ");
        printList(head);
    }
}

Output

Linked List before Sorting: 
0 1 2 2 1 0 1 
Linked List after Sorting: 
0 0 1 1 1 2 2