链表中分治
# 21. 合并两个有序链表 (opens new window)
方法一：归并
class Solution {
public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while(p1!=null && p2!=null){
if(p1.val>p2.val){
p.next = p2;
p2 = p2.next;
}else{
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
if(p1!=null) p.next = p1;
if(p2!=null) p.next = p2;
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
方法二：递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 23. 合并 K 个升序链表 (opens new window)
方法一：归并
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
return sort(lists,0,lists.length-1);
}
ListNode sort(ListNode[] lists,int l,int r){
if(l==r) return lists[l];
int mid = (l+r)>>>1;
ListNode l1 = sort(lists,l,mid);
ListNode l2 = sort(lists,mid+1,r);
return merge(l1,l2);
}
ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next = merge(l1.next,l2);
return l1;
}else{
l2.next = merge(l1,l2.next);
return l2;
}
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
方法二：优先级队列
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->{
return a.val-b.val;
});
for(ListNode head:lists){
if(head!=null){
pq.add(head);
}
}
while(!pq.isEmpty()){
ListNode node = pq.poll();
p.next = node;
if(node.next!=null){
pq.add(node.next);
}
p = p.next;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 148. 排序链表 (opens new window)
class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null)
return head;
ListNode mid = getMid(head);
ListNode rightHead = mid.next;
mid.next = null;
ListNode l = sortList(head);
ListNode r = sortList(rightHead);
return merge(l,r);
}
ListNode getMid(ListNode head){
if(head.next==null || head.next.next==null){
return head;
}
ListNode fast=head,slow=head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
ListNode merge(ListNode l,ListNode r){
ListNode dummy = new ListNode(-1);
ListNode cur= dummy;
while(l!=null && r!=null){
if(l.val>r.val){
cur.next = r;
r = r.next;
}else{
cur.next = l;
l = l.next;
}
cur = cur.next;
}
cur.next = (l!=null?l:r);
return dummy.next;
}
}
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
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
# 86. 分隔链表 (opens new window)
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(-1);// <=x部分
ListNode dummy2 = new ListNode(-1);// >x部分
ListNode p1=dummy1,p2=dummy2;
ListNode p = head;
while(p!=null){
if(p.val>=x){
p2.next = p;
p2 = p2.next;
}else{
p1.next = p;
p1 = p1.next;
}
// 断开原链表中每个节点的next指针
ListNode tmp = p.next;
p.next = null;
p = tmp;
}
// 两部分连接
p1.next = dummy2.next;
return dummy1.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24