目录
题目
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:
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
解决方案
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
49
50
51
52
53
54
55
56
|
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null) return null;
List<ListNode> list1 = new ArrayList<>();
List<ListNode> list2 = new ArrayList<>();
ListNode p = head;
while (p != null) {
if(p.val < x) {
list1.add(p);
} else {
list2.add(p);
}
p = p.next;
}
if(list1.size() == 0 || list2.size() == 0){
return head;
} else {
ListNode head1 = new ListNode(0);
ListNode head2 = new ListNode(0);
ListNode end = null;
ListNode p1 = head1;
ListNode p2 = head2;
for(int m = 0; m < list1.size(); m++){
p1.val = list1.get(m).val;
if(m == list1.size()-1){
p1.next = null;
end = p1;
} else {
p1.next = new ListNode(0);
}
p1 = p1.next;
}
for(int n = 0; n < list2.size(); n++){
p2.val = list2.get(n).val;
if(n == list2.size()-1){
p2.next = null;
} else {
p2.next = new ListNode(0);
}
p2 = p2.next;
}
end.next = head2;
return head1;
}
}
}
|
注意事项
- 遍历一遍，将小于x的放在一个ArrayList中，将大于等于x的放在另一个ArrayList中。之后再分别构造链表，相连起来。
- 思路相同，但是不必放入List在连起来构造链表，这样效率比较低。下面方法直接用指针完成：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public ListNode partition(ListNode head, int x) {
ListNode head1 = new ListNode(0);
ListNode head2 = new ListNode(0);
ListNode curr1 = head1;
ListNode curr2 = head2;
while (head != null){
if (head.val < x) {
curr1.next = head;
curr1 = head;
}else {
curr2.next = head;
curr2 = head;
}
head = head.next;
}
curr2.next = null;
curr1.next = head2.next;
return head1.next;
}
|