Partition a singly linked list. Choose a value x, then place all nodes with values less than x before those with values greater than or equal to x, while preserving the original relative order within each group.
Approach:
First, find the first node with a value less than x and move it to the front.
Then, find the first node with a value greater than or equal to x.
From there, enumerate the remaining nodes: if a node’s value is greater than or equal to x, skip it; if it is less than x, move it before the first node with a value greater than or equal to x.
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
| class Solution {
public:
ListNode *partition(ListNode *head, int x) {
if(head == NULL || head->next == NULL)
return head;
ListNode * beforenode;
ListNode * minnode, *maxnode; // find the 1st minnode
if(head->val < x) {
minnode = head;
}
else {
beforenode = head;
minnode = head->next;
while(minnode != NULL && minnode->val >= x) {
beforenode = minnode;
minnode = minnode->next;
}
if(minnode == NULL) return head;
beforenode->next = minnode->next;
minnode->next = head; // now the head is minnode;
}
beforenode = minnode;
maxnode = minnode->next;
while(maxnode != NULL && maxnode->val < x) {
beforenode = maxnode;
maxnode = maxnode->next;
}
if(maxnode == NULL || maxnode->next == NULL) return minnode;
// now find minnode and maxnode. the head is minnode
head = minnode;
ListNode * now = maxnode->next;
while(now != NULL) {
if(now->val >= x) {
maxnode = now;
now = now->next;
}
else {
ListNode * tmp = beforenode->next;
maxnode->next = now->next;
beforenode->next = now;
now->next = tmp;
now = maxnode->next;
beforenode = beforenode->next;
}
}
return head;
}
};
|