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

Slug: given-a-linked-list-of-0s-1s-and-2s-sort-it Difficulty: Medium Id: 700028 Topic Tags: Linked List, Data Structures Company Tags: Amazon, Microsoft, MakeMyTrip

Summary

Given a linked list consisting of nodes with values either 0, 1 or 2, sort the linked list such that all 0s come first, then all 1s and finally all 2s. This problem involves manipulating a linked list and requires basic knowledge of data structures.

Detailed Explanation

The given problem can be solved by using Dutch National Flag algorithm which is an extension to the QuickSort algorithm for sorting an array or linked list consisting of 0s, 1s and 2s.

Here's a step-by-step breakdown of the solution:

Initialize three pointers, low, mid, high such that low points to the start of the list, mid points to the first node and high points to the last node.
Traverse the linked list. For each node, if it is 0, move low to the next node and keep mid at its current position. If it is 1 or 2, move mid to the next node and high to the next node.
Continue this process until we reach the end of the list.

Here's a visual representation of the algorithm:

          +---+    +---+    +---+
low 0      | 0 |    | 1 |    | 2 |
mid 1      +---+    +---+    +---+
high 3

Time complexity: O(n) Space complexity: O(1)

Optimized Solutions

Java

class Node { int val; Node next; public Node(int val) { this.val = val; } } public class Solution { public void sortColors(Node head) { if (head == null) return; Node low = head, mid = head, high = head; while (mid.next != null) { switch (mid.next.val) { case 0: low = low.next; mid = mid.next; break; case 1: mid = mid.next; break; case 2: high = high.next; mid = mid.next; break; } } } }