23.合并K个升序链表

题目描述

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
1
输入:lists = [[1,4,5],[1,3,4],[2,6]]
2
输出:[1,1,2,3,4,4,5,6]
3
解释:链表数组如下:
4
[
5
1->4->5,
6
1->3->4,
7
2->6
8
]
9
将它们合并到一个有序链表中得到。
10
1->1->2->3->4->4->5->6
Copied!
示例 2:
1
输入:lists = []
2
输出:[]
Copied!
示例 3:
1
输入:lists = [[]]
2
输出:[]
Copied!
提示:
    k == lists.length
    0 <= k <= 10^4
    0 <= lists[i].length <= 500
    -10^4 <= lists[i][j] <= 10^4
    lists[i]升序 排列
    lists[i].length 的总和不超过 10^4

题解

解法一

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
//执行用时: 278 ms
12
//内存消耗: 40.9 MB
13
class Solution {
14
public ListNode mergeKLists(ListNode[] lists) {
15
if(lists == null || lists.length == 0)return null;
16
ListNode cur = lists[0];
17
//遍历所有的链表
18
for(int i = 1;i < lists.length;i++){
19
cur = merge(cur,lists[i]);
20
}
21
return cur;
22
}
23
//两个有序链表合并
24
private ListNode merge(ListNode l1,ListNode l2){
25
if(l1==null)return l2;
26
if(l2==null)return l1;
27
if(l1.val <= l2.val){
28
l1.next = merge(l1.next,l2);
29
return l1;
30
}else{
31
l2.next = merge(l1,l2.next);
32
return l2;
33
}
34
}
35
}
Copied!

解法二分治算法

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode() {}
7
* ListNode(int val) { this.val = val; }
8
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
* }
10
*/
11
//
12
class Solution {
13
public ListNode mergeKLists(ListNode[] lists) {
14
if(lists == null || lists.length == 0) return null;
15
sort(lists,0,lists.length-1);
16
return lists[0];
17
}
18
//参考算法第四版的归并排序
19
//1. 利用sort方法拆分成[1] [2] [3] [4]
20
//2. 归并
21
//和归并排序的区别
22
//merge的时候不需要知道开始和结束的索引
23
private void sort(ListNode[] lists, int lo, int hi) {
24
if (hi <= lo) return;
25
int mid = lo + (hi - lo) / 2;
26
sort(lists, lo, mid); //将左半边排序
27
sort(lists, mid + 1, hi); //将右半边排序
28
lists[lo] = merge(lists[lo],lists[mid+1]); //归并结果
29
lists[mid+1]=null;
30
}
31
private ListNode merge(ListNode l1,ListNode l2){
32
if(l1==null)return l2;
33
if(l2==null)return l1;
34
if(l1.val <= l2.val){
35
l1.next = merge(l1.next,l2);
36
return l1;
37
}else{
38
l2.next = merge(l1,l2.next);
39
return l2;
40
}
41
}
42
}
Copied!
1
//官方分治算法代码
2
class Solution {
3
public ListNode mergeKLists(ListNode[] lists) {
4
return merge(lists, 0, lists.length - 1);
5
}
6
7
public ListNode merge(ListNode[] lists, int l, int r) {
8
if (l == r) {
9
return lists[l];
10
}
11
if (l > r) {
12
return null;
13
}
14
int mid = (l + r) >> 1;
15
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
16
}
17
18
public ListNode mergeTwoLists(ListNode a, ListNode b) {
19
if (a == null || b == null) {
20
return a != null ? a : b;
21
}
22
ListNode head = new ListNode(0);
23
ListNode tail = head, aPtr = a, bPtr = b;
24
while (aPtr != null && bPtr != null) {
25
if (aPtr.val < bPtr.val) {
26
tail.next = aPtr;
27
aPtr = aPtr.next;
28
} else {
29
tail.next = bPtr;
30
bPtr = bPtr.next;
31
}
32
tail = tail.next;
33
}
34
tail.next = (aPtr != null ? aPtr : bPtr);
35
return head.next;
36
}
37
}
Copied!
最近更新 4mo ago