Partition: Write code to partition a linked list around a value x, such that all nodes less than x come before 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). The partition element x can appear anywhere in the “right partition”; it does not need to appear between the left and right partitions.
EXAMPLE
1
2
|
Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition=5]
Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8
|
解法1
弄两个链表，一个放小于x的，一个放大于等于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
|
public Node partition(Node head, int x) {
Node small = null;
Node smallHead = null;
Node large = null;
Node largeHead = null;
Node p = head;
while (p != null) {
if (p.data < x) {
if (small == null) {
small = p;
smallHead = p;
continue;
}
small.next = p;
small = p;
} else {
if (large == null) {
large = p;
largeHead = p;
continue;
}
large.next = p;
large = p;
}
p = p.next;
}
// 这里的large.next要清null，这个是large的尾巴，有可能指向一个small的
if (large != null) {
large.next = null;
}
if (smallHead != null) {
small.next = largeHead;
return smallHead;
}
return largeHead;
}
|
时间复杂度：O(n)
空间复杂度：O(1)，实际上没有另开链表，只是存了几个变量而已。
这个算法保持了元素的稳定性，因为不存在交换。
解法2
把小于x的元素放在链表头部，把大于等于x的元素放在链表尾部。因为本题也没有说要稳定排序，所以是可以的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public Node partition(Node node, int x) {
Node head = head;
Node tail = head;
Node p = head;
while (p != null) {
Node next = p.next;
if (p.data < x) {
// 在头部追加<x的node
p.next = head;
head = p;
} else {
// 在屁股后面追加>=x的node
tail.next = p;
tail = p;
}
p = next;
}
tail.next = null;
return head;
}
|
评论