秒懂【合并K个链表】！超清晰图解一步步拆解。
1.思路
根据题目要求，时间复杂度 O(nlogk)。如果K个升序的链表如果执行两两合并，时间复杂度（n*k^2）不满足要求。这时我们可以借助于堆（复杂度为nlogk）来完成K个链表的排序。
假如链表分别为：1→2、 1→4→5与6，合并之后为：1→1→2→4→5→6，结构如下图所示：
具体思路如下：
第一步： 定义（引用）小顶堆。
小顶堆的最小值存储于堆顶，可以完成从小到大的排序操作。
第二步：每个链表的第一个节点放入堆中。
链表的第一个节点加入到堆中之后，堆会根据链表节点的值进行堆化，将节点值最小的放到堆顶，如下图所示。
第三步：从堆中取出元素（取出的元素为节点值最小的），构成新的链表。
接下来从堆中取出堆顶的节点，并将此节点追加到新链表的末尾。节点出堆之后，它对应链表的下一个节点加入到堆中（条件是：即将加入的节点不为Null）。
从堆中取出堆顶的节点1，将它追加到新链表中去，同时1的后一个节点2入堆，加入堆之后，堆会自己进行堆化，将链表节点值最小的重新放置到堆顶。如下图所示：
之后，再从堆中取出堆顶元素1，将其追加到新链表的末尾，1的后一个节点4入堆，堆再自行进行堆化，堆顶始终保存的是节点值最小的节点，如下图所示：
一直按照此方法来操作，如果一个节点出堆，它的下一个节点为Null，则Null不入堆。这样一来最终堆中的所有节点都会被取完，如下图所示：
第四步：返回新链表的头节点。
如果堆已经空了，这时返回虚拟头结点tmpHead的下一个节点即可。
如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构
2.代码
2.1 Python代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param lists ListNode类一维数组
# @return ListNode类
#
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# write code here
from queue import PriorityQueue
# 1. 定义（引用）小顶堆
heap = PriorityQueue()
# 2. 每个链表的第一个节点放入堆中
for i in range(len(lists)):
# 不为空则加入小顶堆
if lists[i] is not None:
heap.put((lists[i].val, i)) # 注意:加入的是元组（优先级,值）
lists[i] = lists[i].next # 移动指针变量，lists[i]执行下一个节点
# 3. 从堆中取出元素（取出的元素为节点值最小的），构成新的链表
tmp_head = ListNode(-1)
cur = tmp_head
# 从堆中取元素（节点），直到小顶堆为空
while not heap.empty():
# 取出最小的元素
val, idx = heap.get() # 注意:取出来的值也是元组，即优先级、值（优先级的值越小（优先级越高），越先取出来）
# 节点连接
cur.next = ListNode(val)
cur = cur.next
if lists[idx] is not None:
# 取出（元素）节点的下一个节点值添加到堆中
heap.put((lists[idx].val, idx))
lists[idx] = lists[idx].next # lists[i]保存下一个节点
# 4. 返回新链表的头节点
return tmp_head.next
2.2 Java代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode类ArrayList
* @return ListNode类
*/
public ListNode mergeKLists (ArrayList<ListNode> lists) {
// write code here
// 1. 定义（引用）小顶堆
Queue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
//默认：小顶堆
return o1.val - o2.val;
}
});
// 2. 每个链表的第一个节点放入堆中
//遍历所有链表第一个元素
for (int i = 0; i < lists.size(); i++) {
//不为空则加入小顶堆
if (lists.get(i) != null) {
heap.add(lists.get(i));
}
}
// 3. 从堆中取出元素（取出的元素为节点值最小的），构成新的链表
ListNode tmpHead = new ListNode(-1);
ListNode cur = tmpHead;
//从堆中取元素（节点），直到小顶堆为空
while (!heap.isEmpty()) {
//取出最小的元素
ListNode tmp = heap.poll();
//节点连接
cur.next = tmp;
cur = cur.next;
//取出（元素）节点的下一个节点添加到堆中
if (tmp.next != null) {
heap.add(tmp.next);
}
}
// 4. 返回新链表的头节点
return tmpHead.next;
}
}
2.3 Go代码
package main
import . "nc_tools"
import "container/heap"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param lists ListNode类一维数组
* @return ListNode类
*/
func mergeKLists(lists []*ListNode) *ListNode {
// write code here
// 1. 定义（引用）小顶堆
myHeap := &MyHeap{}
heap.Init(myHeap)
// 2. 每个链表的第一个节点放入堆中
//遍历所有链表第一个元素
for i := 0; i < len(lists); i++ {
//不为空则加入小顶堆
if lists[i] != nil {
heap.Push(myHeap, lists[i])
}
}
// 3. 从堆中取出元素（取出的元素为节点值最小的），构成新的链表
tmpHead := &ListNode{Val: -1}
cur := tmpHead
//从堆中取元素（节点），直到小顶堆为空
for myHeap.Len() > 0 {
//取出最小的元素
tmp := heap.Pop(myHeap).(*ListNode)
//节点连接
cur.Next = tmp
cur = cur.Next
//取出（元素）节点的下一个节点添加到堆中
if tmp.Next != nil {
heap.Push(myHeap, tmp.Next)
}
}
// 4. 返回新链表的头节点
return tmpHead.Next
}
type MyHeap []*ListNode
func (h MyHeap) Len() int {
return len(h)
}
func (h MyHeap) Less(i, j int) bool {
//小顶堆
return h[i].Val < h[j].Val
}
func (h MyHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *MyHeap) Push(v interface{}) {
*h = append(*h, v.(*ListNode))
}
func (h *MyHeap) Pop() interface{} {
old := *h
n := len(old)
v := old[n-1]
*h = old[0 : n-1]
return v
}
如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构
京公网安备 11010502036488号