05 August 2008
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
要求把小于x的元素按顺序放到链表前面。使用链表最常用的双指针，一个指向当前小于x的最后一个元素，一个进行往前扫描。如果元素大于x，那么继续前进，否则，要把元素移到前面，并更新第一个指针。这里有一个小细节，就是如果不需要移动（也就是已经是接在小于x的最后元素的后面了），那么只需要继续前进即可。算法时间复杂度是O(n)，空间只需要几个辅助变量，是O(1)。
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy, fast = dummy;
while (fast.next != null) {//相当于从dummy.next开始
if (fast.next.val < x) {
if (slow != fast) {//开始把结点插入到前面(slow后面)
ListNode next = fast.next.next;//先记住fast.next的下一位
fast.next.next = slow.next;
slow.next = fast.next;
fast.next = next;//最后把新的fast的next指向开始记住的下一位
} else {//如果slow和fast相同就只需让fast前移
fast = fast.next;
}
slow = slow.next;
} else {//结点的值大于等于x
fast = fast.next;
}
}
return dummy.next;
}
}
另一种写法，新开两条链表分别记录较大和较小得值，然后链接到一起，时间和空间复杂度都是O（n）
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallHead = new ListNode(-1);
ListNode bigHead = new ListNode(-1);
ListNode small = smallHead;
ListNode big = bigHead;
while (head != null) {
ListNode temp = new ListNode(head.val);
if (head.val < x) {
small.next = temp;
small = small.next;
} else {
big.next = temp;
big = big.next;
}
head = head.next;
}
small.next = bigHead.next;
return smallHead.next;
}
}