Partition Linked List
Write code to partition a linked list around a value x, such athat all nodes less than x come befor all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below)
EXAMPLE
Input: 3->5->8->5->10->2->1 [partition = 5]
Output: 3->1->2->10->5->5->8
Solution
用 dummy node 即可
Complexity
时间复杂度 O(n),空间复杂度 O(1)
Code
public static Node partitionStable(Node head, int x){
Node minStart = null;
Node minEnd = null;
Node maxStart = null;
Node maxEnd = null;
while (head != null){
Node next = head.next;
head.next = null;
if (head.data < x){
if (minStart == null){
minStart = head;
minEnd = minStart;
}
else{
minEnd.next = head;
minEnd = head;
}
}
else{
if(maxStart == null){
maxStart = head;
maxEnd = maxStart;
}
else{
maxEnd.next = head;
maxEnd = head;
}
}
head = next;
}
if (minStart == null){
return maxStart;
}
minEnd.next = maxStart;
return minStart;
}
public static Node partitionUnstable(Node head, int x){
Node start = head;
Node end = head;
while (head != null){
Node next = head.next;
if (head.data < x){
head.next = start;
start = head;
}
else{
end.next = head;
end = head;
}
head = next;
}
end.next = null;
return start;
}