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.
Here’s the [Problem Link] to begin with.
Examples:
Input: head = 1 → 2 → 2 → 1 → 2 → 0 → 2 → 2
Output: 0 → 1 → 1 → 2 → 2 → 2 → 2 → 2Explanation: 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.
Input: head = 2 → 2 → 0 → 1
Output: 0 → 1 → 2 → 2Explanation: After arranging all the 0s, 1s and 2s in the given format, the output will be 0 → 1 → 2 → 2.
Constraints:
1 ≤ no. of nodes ≤ 106
0 ≤ node->data ≤ 2
Solution 1: Brute Force Approach (Count and Replace)
Intuition
Think of this like organizing colored balls in a box! You have three colors – let’s say red (0), blue (1), and green (2) balls mixed up. One simple way to organize them is to first count how many balls of each color you have, then arrange them in order. You’d put all red balls first, then all blue balls, then all green balls. We use the same idea here – count all the 0s, 1s, and 2s, then replace the values in the original list.
Detailed Approach
- Count Phase: Walk through the entire linked list and count how many 0s, 1s, and 2s we have
- Replace Phase: Walk through the linked list again and replace values in order
- Fill 0s First: Replace the first
count0nodes with 0 - Fill 1s Next: Replace the next
count1nodes with 1 - Fill 2s Last: Replace the remaining
count2nodes with 2
Code
class Solution:
def segregate(self, head):
if head is None or head.next is None:
return head # Empty list or single node - already sorted
temp = head
cnt0, cnt1, cnt2 = 0, 0, 0 # Counters for 0s, 1s, and 2s
# First pass: Count occurrences of each value
while temp:
if temp.data == 0:
cnt0 += 1 # Count 0s
elif temp.data == 1:
cnt1 += 1 # Count 1s
else:
cnt2 += 1 # Count 2s
temp = temp.next
temp = head # Reset pointer to head for second pass
# Second pass: Replace values with sorted order
# Fill first cnt0 nodes with 0
for _ in range(cnt0):
temp.data = 0
temp = temp.next
# Fill next cnt1 nodes with 1
for _ in range(cnt1):
temp.data = 1
temp = temp.next
# Fill remaining cnt2 nodes with 2
for _ in range(cnt2):
temp.data = 2
temp = temp.next
return headCode Explanation
We use a two-pass approach here. In the first pass, we count how many times each value (0, 1, and 2) appears in the linked list. In the second pass, we go through the linked list again and replace the values in sorted order. We first fill the required number of nodes with 0s, then with 1s, and finally with 2s. This ensures all values are arranged in ascending order.
Dry Run
Let’s trace through: 1 -> 0 -> 2 -> 1 -> 0
First Pass (Count Values):
- Visit node 1: cnt0=0, cnt1=1, cnt2=0
- Visit node 0: cnt0=1, cnt1=1, cnt2=0
- Visit node 2: cnt0=1, cnt1=1, cnt2=1
- Visit node 1: cnt0=1, cnt1=2, cnt2=1
- Visit node 0: cnt0=2, cnt1=2, cnt2=1
Second Pass (Replace Values):
- Fill 2 nodes with 0:
0 -> 0 -> 2 -> 1 -> 0 - Fill 2 nodes with 1:
0 -> 0 -> 1 -> 1 -> 0 - Fill 1 node with 2:
0 -> 0 -> 1 -> 1 -> 2
Result: 0 -> 0 -> 1 -> 1 -> 2
Time and Space Complexity
- Time Complexity: O(n) – We traverse the list twice, but it’s still linear
- Space Complexity: O(1) – We only use a few counter variables
Simplifying It
This approach is like taking inventory first, then organizing. You count everything you have, then arrange them in the right order. It’s straightforward but requires two passes through the list – one to count, one to replace.
Solution 2: Optimal Approach (Three Separate Lists)
Intuition
Imagine you have three separate boxes labeled “0s”, “1s”, and “2s”. Instead of counting first, you can directly sort items as you see them! As you go through the mixed items, you put each item directly into its correct box. At the end, you just connect all three boxes in order – first the 0s box, then the 1s box, then the 2s box.
Detailed Approach
- Create Three Lists: Set up three separate linked lists for 0s, 1s, and 2s using dummy nodes
- Sort While Traversing: Go through the original list and put each node into its correct list
- Track Tails: Keep track of the last node in each list to add new nodes easily
- Connect Lists: Connect the three lists in order: 0s → 1s → 2s
- Handle Empty Lists: Make sure to handle cases where some lists might be empty
Code
class Solution:
def segregate(self, head):
# Create three dummy nodes to start three separate lists
zeroD = Node(0) # Dummy node for 0s list
oneD = Node(1) # Dummy node for 1s list
twoD = Node(2) # Dummy node for 2s list
# Initialize pointers to track the end of each list
zero = zeroD # Current end of 0s list
one = oneD # Current end of 1s list
two = twoD # Current end of 2s list
curr_node = head # Pointer to traverse original list
# Traverse the original list and distribute nodes
while curr_node:
# Check current node's value and add to appropriate list
if curr_node.data == 0:
zero.next = curr_node # Add to 0s list
zero = zero.next # Move 0s list pointer
elif curr_node.data == 1:
one.next = curr_node # Add to 1s list
one = one.next # Move 1s list pointer
else:
two.next = curr_node # Add to 2s list
two = two.next # Move 2s list pointer
curr_node = curr_node.next
# Connect the three lists: 0s -> 1s -> 2s
if oneD.next:
zero.next = oneD.next # Connect 0s to 1s if 1s exist
else:
zero.next = twoD.next # Connect 0s to 2s if no 1s exist
one.next = twoD.next # Connect 1s to 2s
two.next = None # End the final list
return zeroD.next # Return head of sorted list (skip dummy)Code Explanation
We create three separate linked lists using dummy nodes as starting points. As we traverse the original list, we move each node to its appropriate list based on its value. We keep track of the tail of each list so we can easily add new nodes. Finally, we connect the three lists in order: all 0s first, then all 1s, then all 2s. We handle the case where some lists might be empty by checking before connecting.
Dry Run
Let’s trace through: 1 -> 0 -> 2 -> 1 -> 0
Initial Setup:
- zeroD → (dummy), oneD → (dummy), twoD → (dummy)
- zero = zeroD, one = oneD, two = twoD
Process Each Node:
- Node 1: Add to 1s list → oneD → 1
- Node 0: Add to 0s list → zeroD → 0
- Node 2: Add to 2s list → twoD → 2
- Node 1: Add to 1s list → oneD → 1 → 1
- Node 0: Add to 0s list → zeroD → 0 → 0
Connect Lists:
- 0s list: zeroD → 0 → 0
- 1s list: oneD → 1 → 1
- 2s list: twoD → 2
- Connect: 0 → 0 → 1 → 1 → 2
Result: 0 → 0 → 1 → 1 → 2
Time and Space Complexity
- Time Complexity: O(n) – We traverse the list only once
- Space Complexity: O(1) – We only use a few pointer variables (dummy nodes don’t count as extra space)
Simplifying It
This approach is like having three separate conveyor belts – one for each value. As items come in, you immediately put them on the correct belt. At the end, you just connect the three belts in order. More efficient since you only need one pass through the original list!
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Count & Replace) | O(n) | O(1) | Easy | Learning the concept |
| Optimal (Three Lists) | O(n) | O(1) | Medium | Production code |
The optimal approach is generally preferred because it solves the problem in a single pass while using the same space complexity. However, the brute force approach is more intuitive and easier to understand when you’re first learning about linked list manipulation.
Both solutions effectively solve the problem with the same time and space complexity, but the optimal solution is more elegant because it sorts the nodes in one pass. The key insight is that when you only have three possible values, you can create separate “buckets” for each value and then combine them, which is much more efficient than general sorting algorithms!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
