PROBLEM DESCRIPTION
Given a linked list where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to the head side, 2s at the end of the linked list, and 1s in the middle of 0s and 2s.
SOLUTION
We can iterate over the nodes in the original list and use these nodes to create three linked lists (only by changing the pointers). The first list will have only nodes with 0 values, 2nd will have only the nodes with 1 as the value and 3rd list with 2 value nodes. Once we have these three lists, we can just point the first list’s tail to head of second list. If second list is null, then it should point to third list. Similarly, second list should point to third list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
static Node segregate(Node head) {
// Create three head pointers for lists of 0s, 1s, and 2s
Node h0 = null, h1 = null, h2 = null;
// Create tail pointers for the lists of 0s, 1s, and 2s
Node t0 = null, t1 = null, t2 = null;
// Pointer to traverse the original linked list
Node current = head;
// Traverse the original linked list
while(current != null){
// Store the next node temporarily, as current node's next will be altered
Node nextNode = current.next;
// If the current node contains data 0
if(current.data == 0){
// Add the node to the list of 0s
current.next = h0;
h0 = current;
// If tail of 0s list is null, update it to point to the current node
if(t0 == null)
t0 = current;
} else if(current.data == 1){ // If the current node contains data 1
// Add the node to the list of 1s
current.next = h1;
h1 = current;
// If tail of 1s list is null, update it to point to the current node
if(t1 == null)
t1 = current;
} else { // If the current node contains data 2
// Add the node to the list of 2s
current.next = h2;
h2 = current;
// If tail of 2s list is null, update it to point to the current node
if(t2 == null)
t2 = current;
}
// Move to the next node in the original list
current = nextNode;
}
// Now, connect the three separate lists: 0s -> 1s -> 2s
// If there's a list of 0s, connect its tail to the head of the 1s list
if(t0 != null){
if(h1 != null)
t0.next = h1;
else
t0.next = h2; // If no 1s, connect it to the 2s list
}
// If there's a list of 1s, connect its tail to the head of the 2s list
if(t1 != null)
t1.next = h2;
// Return the head of the new sorted list, starting with 0s, 1s, or 2s
if(h0 != null)
return h0;
else if(h1 != null)
return h1;
else
return h2;
}
}