【day10】链表的合并

题目 1:合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

思路:采用递归的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val >= list2.val){
list2.next = mergeTwoLists(list1,list2.next);
return list2;
}else{
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
}
}

题目 2:合并 K 个升序链表

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路 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
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if(len == 0){
return null;
}else if(len == 1){
return lists[0];
}
ListNode ans = lists[0];
for (int i = 1; i < len; i++) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val >= list2.val) {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
} else {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
}
}

在这里插入图片描述

由于这个算法的时间复杂度为 O(k^2*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
33
34
35
36
37
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}

public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}

public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}

在这里插入图片描述
优化成分治,使得在遍历 lists 时的时间复杂度大大降低:
在这里插入图片描述


【day10】链表的合并
http://blog.luliang.online/2023/03/22/【day10】链表的合并/
作者
Luyoung
发布于
2023年3月22日
许可协议