leetcode.Q23.合并K个升序链表

解析思路

leetcode 困难,题目描述点击这里

本题属于多路归并类题型。解法也是多路归并,但是怎么归呢?

对于两个有序链表的合并可以通过直接比较链表头的元素大小,将小的拿出来放到新的链表中,但是直接比较无法用于链表数不确定的情况。对于多路归并主要有以下几种办法:

  1. 依次归并.先让第 1 和第 2 做二路归并,将结果再和第 3 做二路归并,知道全部归并完毕
  2. 分治法.先将链表两两做二路归并,此次链表数变成 n/2(链表数为奇数时 n/2+1),然后再对结果两两做二路归并,知道最后只剩两条,继续归并即得到结果
  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
public ListNode so1(ListNode[] lists) {
List<ListNode> listNodeList = Arrays.stream(lists).filter(Objects::nonNull).collect(Collectors.toList());
if (listNodeList.isEmpty()) {
return null;
}
ListNode res = listNodeList.get(0);
for (int i = 1; i < listNodeList.size(); i++) {
//依次和第i合并
ListNode tempRes = new ListNode(), temp = tempRes;
ListNode cur = listNodeList.get(i);
while (res != null && cur != null) {
if (res.val < cur.val) {
temp.next = res;
res = res.next;
} else {
temp.next = cur;
cur = cur.next;
}
temp = temp.next;
}
//接上剩下的部分
temp.next = res == null ? cur : res;
//临时结果
res = tempRes.next;
}
return res;
}

分治法

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
public ListNode so2(ListNode[] lists) {
List<ListNode> listNodeList = Arrays.stream(lists).filter(Objects::nonNull).collect(Collectors.toList());
int n = listNodeList.size();
if (n == 0) {
return null;
}
while (n > 1) {
int count = 0;
for (int i = 0; i + 1 < n; i += 2, count++) {
ListNode a = listNodeList.get(i), b = listNodeList.get(i + 1), head = new ListNode(), temp = head;
while (a != null && b != null) {
if (a.val < b.val) {
temp.next = a;
a = a.next;
} else {
temp.next = b;
b = b.next;
}
temp = temp.next;
}
temp.next = a == null ? b : a;
listNodeList.set(count, head.next);
}
//如果为奇数,要把最后一个落单的放到count上
if (n % 2 != 0) {
listNodeList.set(count++, listNodeList.get(n - 1));
}
//新的链表数量为count
n = count;
}
return listNodeList.get(0);
}

优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
queue.addAll(Arrays.stream(lists).filter(Objects::nonNull).collect(Collectors.toList()));
if (queue.isEmpty()) {
return null;
}
ListNode res = queue.poll(), temp = res;
while (!queue.isEmpty()) {
if (temp.next != null) {
queue.add(temp.next);
}
temp.next = queue.poll();
temp = temp.next;
}
return res;
}

本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号