# 05. Sort a Linked List of 0s, 1s and 2s
The problem can be found at the following link: π [Question Link](https://www.geeksforgeeks.org/problems/given-a-linked-list-of-0s-1s-and-2s-sort-it/1)
## **𧩠Problem Description**
Given the head of a linked list where nodes can contain values **0s, 1s, and 2s only**. Your task is to rearrange the list so that all **0s appear at the beginning**, followed by all **1s**, and all **2s are placed at the end**.
A linked list is a linear data structure where elements are stored in nodes, and each node contains data and a reference to the next node. The goal is to segregate the nodes based on their data values while maintaining the relative order within each group.
## **π Examples**
### Example 1
```cpp
Input: head = 1 β 2 β 2 β 1 β 2 β 0 β 2 β 2
Output: 0 β 1 β 1 β 2 β 2 β 2 β 2 β 2
Explanation: All the 0s are segregated to the left end of the linked list, 2s to the right end of the list, and 1s in between.
```
### Example 2
```cpp
Input: head = 2 β 2 β 0 β 1
Output: 0 β 1 β 2 β 2
Explanation: After arranging all the 0s, 1s and 2s in the given format, the output will be sorted.
```
## **π Constraints**
* $1 \le \text{no. of nodes} \le 10^6$
* $0 \le \text{node->data} \le 2$
## **β
My Approach**
The optimal approach uses **Three-Way Partitioning** with **Pointer Manipulation** to efficiently segregate nodes without using extra space for new nodes:
### **Node Segregation with Tail Pointers**
1. **Initialize Pointers:**
* Create separate head and tail pointers for each category: `zero`, `one`, `two` (heads) and `zeroTail`, `oneTail`, `twoTail` (tails).
* All pointers initially set to `nullptr`.
2. **Traverse and Segregate:**
* Iterate through the original list, breaking the `next` links to isolate each node.
* Based on node data (0, 1, or 2), append the node to the respective category list.
* Update both head and tail pointers for efficient O(1) appending.
3. **Link Categories:**
* Connect the three segregated lists: `zeros β ones β twos`.
* Handle edge cases where any category might be empty.
* Determine the final head based on which categories exist.
4. **Return Result:**
* Return the head of the newly constructed segregated list.
## π Time and Auxiliary Space Complexity
* **Expected Time Complexity:** O(n), where n is the number of nodes in the linked list. We traverse each node exactly once to segregate them into three categories.
* **Expected Auxiliary Space Complexity:** O(1), as we only use a constant amount of additional space for pointer variables, regardless of the input size. No extra nodes are created.
## **π§βπ» Code (C++)**
```cpp
class Solution {
public:
Node* segregate(Node* head) {
if (!head) return head;
Node* zero = nullptr, *one = nullptr, *two = nullptr;
Node* zeroTail = nullptr, *oneTail = nullptr, *twoTail = nullptr;
while (head) {
Node* next = head->next;
head->next = nullptr;
if (head->data == 0) {
if (!zero) zero = zeroTail = head;
else zeroTail = zeroTail->next = head;
} else if (head->data == 1) {
if (!one) one = oneTail = head;
else oneTail = oneTail->next = head;
} else {
if (!two) two = twoTail = head;
else twoTail = twoTail->next = head;
}
head = next;
}
if (zeroTail) {
head = zero;
zeroTail->next = one ? one : two;
if (oneTail) oneTail->next = two;
} else if (oneTail) {
head = one;
oneTail->next = two;
} else {
head = two;
}
return head;
}
};
```
β‘ View Alternative Approaches with Code and Analysis
### π **2οΈβ£ In-Place Data Modification Approach**
#### π‘ Algorithm Steps:
1. First pass: Count occurrences of 0s, 1s, and 2s while traversing the list.
2. Second pass: Overwrite node data values in order - first all 0s, then all 1s, finally all 2s.
3. Preserve the original node structure while only modifying data values.
4. Return the head of the modified list with sorted data.
```cpp
class Solution {
public:
Node* segregate(Node* head) {
vector count(3, 0);
for (Node* temp = head; temp; temp = temp->next)
count[temp->data]++;
Node* curr = head;
for (int i = 0; i < 3; i++) {
while (count[i]-- && curr) {
curr->data = i;
curr = curr->next;
}
}
return head;
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Two passes through the list
* **Auxiliary Space:** πΎ O(1) - Only counter array of size 3
#### β
**Why This Approach?**
* Simplest logic with counting approach
* Preserves original node addresses and structure
* Minimal memory overhead with fixed-size array
### π **3οΈβ£ Single Pass with Tail Pointers**
#### π‘ Algorithm Steps:
1. Use single pass with immediate node segregation and linking.
2. Maintain separate head and tail pointers for each of the three categories.
3. Break original connections and establish new ones during traversal.
4. Handle all edge cases with conditional linking at the end.
```cpp
class Solution {
public:
Node* segregate(Node* head) {
Node *zHead = nullptr, *zTail = nullptr;
Node *oHead = nullptr, *oTail = nullptr;
Node *tHead = nullptr, *tTail = nullptr;
while (head) {
if (head->data == 0) {
if (!zHead) zHead = zTail = head;
else zTail->next = head, zTail = head;
} else if (head->data == 1) {
if (!oHead) oHead = oTail = head;
else oTail->next = head, oTail = head;
} else {
if (!tHead) tHead = tTail = head;
else tTail->next = head, tTail = head;
}
Node* temp = head->next;
head->next = nullptr;
head = temp;
}
if (zTail) zTail->next = oHead ? oHead : tHead;
if (oTail) oTail->next = tHead;
return zHead ? zHead : (oHead ? oHead : tHead);
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Single pass through list
* **Auxiliary Space:** πΎ O(1) - Only pointer variables
#### β
**Why This Approach?**
* Optimal single-pass solution without extra traversals
* No dummy nodes required, direct manipulation
* Efficient node relinking with O(1) operations per node
### π **4οΈβ£ Recursive Segregation**
#### π‘ Algorithm Steps:
1. Use recursion to process nodes from head to tail systematically.
2. Maintain global pointers for each category to build segregated lists.
3. Process current node and recursively handle the rest of the list.
4. Link the three categories together during the base case return.
```cpp
class Solution {
Node *zHead = nullptr, *oHead = nullptr, *tHead = nullptr;
Node *zTail = nullptr, *oTail = nullptr, *tTail = nullptr;
void processNode(Node* node) {
if (!node) return;
Node* next = node->next;
node->next = nullptr;
if (node->data == 0) {
if (!zHead) zHead = zTail = node;
else zTail->next = node, zTail = node;
} else if (node->data == 1) {
if (!oHead) oHead = oTail = node;
else oTail->next = node, oTail = node;
} else {
if (!tHead) tHead = tTail = node;
else tTail->next = node, tTail = node;
}
processNode(next);
}
public:
Node* segregate(Node* head) {
zHead = oHead = tHead = zTail = oTail = tTail = nullptr;
processNode(head);
if (zTail) zTail->next = oHead ? oHead : tHead;
if (oTail) oTail->next = tHead;
return zHead ? zHead : (oHead ? oHead : tHead);
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Single recursive traversal
* **Auxiliary Space:** πΎ O(n) - Recursive call stack space
#### β
**Why This Approach?**
* Elegant recursive solution with clear logic flow
* Good for educational purposes and functional programming
* Clear separation of processing and linking phases
### π **5οΈβ£ Dutch National Flag Algorithm Adaptation**
#### π‘ Algorithm Steps:
1. Adapt the classic Dutch National Flag algorithm for linked lists.
2. Use three pointers to mark boundaries of 0s, 1s, and 2s regions.
3. Swap node data values instead of array elements to maintain list structure.
4. Continue until all nodes are properly segregated into three regions.
```cpp
class Solution {
public:
Node* segregate(Node* head) {
if (!head || !head->next) return head;
Node* curr = head;
int count0 = 0, count1 = 0, count2 = 0;
while (curr) {
if (curr->data == 0) count0++;
else if (curr->data == 1) count1++;
else count2++;
curr = curr->next;
}
curr = head;
while (count0 > 0) {
curr->data = 0;
curr = curr->next;
count0--;
}
while (count1 > 0) {
curr->data = 1;
curr = curr->next;
count1--;
}
while (count2 > 0) {
curr->data = 2;
curr = curr->next;
count2--;
}
return head;
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Two passes through the list
* **Auxiliary Space:** πΎ O(1) - Only counting variables
#### β
**Why This Approach?**
* Classic algorithm adaptation for linked list context
* Simple counting and reconstruction approach
* Maintains original node structure with data modification
### π **π Comparison of Approaches**
| π **Approach** | β±οΈ **Time Complexity** | πΎ **Space Complexity** | β
**Pros** | β οΈ **Cons** |
| ---------------------------- | ---------------------- | ----------------------- | --------------------------------- | -------------------------------- |
| π **Node Relinking** | π’ O(n) | π’ O(1) | π Preserves nodes, optimal space | π§ Complex pointer management |
| π **Data Modification** | π’ O(n) | π’ O(1) | π Simplest logic | π Modifies original data values |
| π― **Single Pass Linking** | π’ O(n) | π’ O(1) | β No dummy nodes, efficient | π§ Multiple edge case handling |
| π **Recursive** | π’ O(n) | π‘ O(n) | π¨ Elegant and educational | π Extra stack space overhead |
| π΄ **Dutch Flag Adaptation** | π’ O(n) | π’ O(1) | π― Classic algorithm pattern | π Two-pass approach |
#### π **Best Choice Recommendation**
| π― **Scenario** | ποΈ **Recommended Approach** | π₯ **Performance Rating** |
| ------------------------------------------ | ----------------------------- | ------------------------- |
| π
**Memory constrained environments** | π₯ **Data Modification** | β
β
β
β
β
|
| π **Production code, maintainability** | π₯ **Single Pass Linking** | β
β
β
β
β |
| π§ **Node identity preservation required** | π₯ **Node Relinking** | β
β
β
β
β
|
| π― **Educational/Interview contexts** | π
**Recursive** | β
β
β
ββ |
| π **Algorithm pattern demonstration** | ποΈ **Dutch Flag Adaptation** | β
β
β
β
β |
## **β Code (Java)**
```java
class Solution {
public Node segregate(Node head) {
if (head == null) return head;
Node zero = null, one = null, two = null;
Node zTail = null, oTail = null, tTail = null;
while (head != null) {
Node next = head.next;
head.next = null;
if (head.data == 0) {
if (zero == null) zero = zTail = head;
else zTail = zTail.next = head;
} else if (head.data == 1) {
if (one == null) one = oTail = head;
else oTail = oTail.next = head;
} else {
if (two == null) two = tTail = head;
else tTail = tTail.next = head;
}
head = next;
}
if (zTail != null) {
head = zero;
zTail.next = (one != null) ? one : two;
if (oTail != null) oTail.next = two;
} else if (oTail != null) {
head = one;
oTail.next = two;
} else {
head = two;
}
return head;
}
}
```
## **π Code (Python)**
```python
class Solution:
def segregate(self, head):
if not head:
return head
zero = one = two = None
z_tail = o_tail = t_tail = None
while head:
next_node = head.next
head.next = None
if head.data == 0:
if not zero:
zero = z_tail = head
else:
z_tail.next = head
z_tail = head
elif head.data == 1:
if not one:
one = o_tail = head
else:
o_tail.next = head
o_tail = head
else:
if not two:
two = t_tail = head
else:
t_tail.next = head
t_tail = head
head = next_node
if z_tail:
head = zero
z_tail.next = one if one else two
if o_tail:
o_tail.next = two
elif o_tail:
head = one
o_tail.next = two
else:
head = two
return head
```
## π§ Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [π¬ Any Questions?](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let's make this learning journey more collaborative!
β **If you find this helpful, please give this repository a star!** β
***
#### πVisitor Count
