题目
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入:
1
| head = 1->4->3->2->5->2, x = 3
|
输出:
要求
每部分中结点从左到右顺序与原链表的先后次序一致
题解
可创建三个指针分别保存三个部分的结点, 新结点追加即可
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
| class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class PartitionList {
public static ListNode partition(ListNode head, int x) {
ListNode left = new ListNode(0);
ListNode middle = new ListNode(0);
ListNode right = new ListNode(0);
ListNode node1 = left;
ListNode node2 = middle;
ListNode node3 = right;
while (head != null) {
if (head.val < x) {
node1.next = head;
head = head.next;
node1 = node1.next;
node1.next = null;
} else if (head.val == x) {
node2.next = head;
head = head.next;
node2 = node2.next;
node2.next = null;
} else {
node3.next = head;
head = head.next;
node3 = node3.next;
node3.next = null;
}
}
node1.next = middle.next;
node2.next = right.next;
return left.next;
}
}
|
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入:
1
| head = 1->4->3->2->5->2, x = 3
|
输出:
Java
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
| class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public class PartitionList {
public static ListNode partition(ListNode head, int x) {
ListNode left = new ListNode(0);
ListNode right = new ListNode(0);
ListNode node1 = left;
ListNode node2 = right;
while (head != null) {
if (head.val < x) {
node1.next = head;
head = head.next;
node1 = node1.next;
node1.next = null;
} else {
node2.next = head;
head = head.next;
node2 = node2.next;
node2.next = null;
}
}
node1.next = right.next;
return left.next;
}
}
|
Python
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
| class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class PartitionList:
def partition(self, head, x):
left = ListNode(0)
right = ListNode(0)
node1 = left
node2 = right
while head:
if head.val < x:
node1.next = head
head = head.next
node1 = node1.next
node1.next = None
else:
node2.next = head
head = head.next
node2 = node2.next
node2.next = None
node1.next = right.next
return left.next
|