可视化图解算法合并k个已排序升序的链表
可视化图解算法：合并k个已排序（升序）的链表
1. 题目
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数满足 0≤ n ≤105，链表个数满足 1≤ k ≤105 ，每个链表的长度满足 1≤len≤200 ，每个节点的值满足∣ val ∣<=1000
要求：时间复杂度 O(nlogk)
示例1
输入：
[{1,2,3},{4,5,6,7}]返回值：
{1,2,3,4,5,6,7}示例2
输入：
[{1,2},{1,4,5},{6}]返回值：
{1,1,2,4,5,6}2. 解题思路
根据题目要求，时间复杂度 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的下一个节点即可。
如果文字描述的不太清楚，你可以参考视频的详细讲解。
Python版本： [哔哩哔哩_bilibili
“哔哩哔哩_bilibili”)Java版本： [数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili
数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
“数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili”)Golang版本： [哔哩哔哩_bilibili
“哔哩哔哩_bilibili”)
“哔哩哔哩_bilibili”)3. 编码实现
3.1 Python编码实现
from typing import List
from queue import PriorityQueue
class ListNode:
def __init__(self, x):
self.val = x # 链表的数值域
self.next = None # 链表的指针域
# 从链表节点尾部添加节点
def insert_node(node, value):
if node is None:
print("node is None")
return
# 创建一个新节点
new_node = ListNode(value)
cur = node
# 找到链表的末尾节点
while cur.next is not None:
cur = cur.next
# 末尾节点的next指针域连接新节点
cur.next = new_node
# 打印链表（从链表头结点开始打印链表的值）
def print_node(node):
cur = node
# 遍历每一个节点
while cur is not None:
print(cur.val, end="\t")
cur = cur.next # 更改指针变量的指向
print()
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param lists ListNode类一维数组
# @return ListNode类
#
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
# write code here
# 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
if __name__ == '__main__':
list1 = ListNode(1)
list1.next = ListNode(2)
print_node(list1)
list2 = ListNode(1)
list2.next = ListNode(4)
list2.next.next = ListNode(5)
print_node(list2)
list3 = ListNode(6)
print_node(list3)
old_list = [list1, list2, list3]
s = Solution()
new_list = s.mergeKLists(old_list)
print_node(new_list)3.2 Java编码实现
package LL05;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
//定义链表节点
static class ListNode {
private int val; //链表的数值域
private ListNode next; //链表的指针域
public ListNode(int data) {
this.val = data;
this.next = null;
}
}
//添加链表节点
private static void insertNode(ListNode node, int data) {
if (node == null) {
return;
}
//创建一个新节点
ListNode newNode = new ListNode(data);
ListNode cur = node;
//找到链表的末尾节点
while (cur.next != null) {
cur = cur.next;
}
//末尾节点的next指针域连接新节点
cur.next = newNode;
}
//打印链表（从头节点开始打印链表的每一个节点）
private static void printNode(ListNode node) {
ListNode cur = node;
//遍历每一个节点
while (cur != null) {
System.out.print(cur.val + "\t");
cur = cur.next; //更改指针变量的指向
}
System.out.println();
}
public static 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;
}
}
public static void main(String[] args) {
ListNode list1 = new ListNode(1);
list1.next = new ListNode(2);
printNode(list1);
ListNode list2 = new ListNode(1);
list2.next = new ListNode(4);
list2.next.next = new ListNode(5);
printNode(list2);
ListNode list3 = new ListNode(6);
printNode(list3);
ArrayList<ListNode> lists = new ArrayList<>();
lists.add(list1);
lists.add(list2);
lists.add(list3);
Solution solution = new Solution();
ListNode newList = solution.mergeKLists(lists);
printNode(newList);
}
}3.3 Golang编码实现
package main
import (
"container/heap"
"fmt"
)
// ListNode 定义链表节点
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
}
func main() {
list1 := &ListNode{Val: 1}
list1.Next = &ListNode{Val: 2}
list1.Print()
list2 := &ListNode{Val: 1}
list2.Next = &ListNode{Val: 4}
list2.Next.Next = &ListNode{Val: 5}
list2.Print()
list3 := &ListNode{Val: 6}
list3.Print()
lists := []*ListNode{list1, list2, list3}
newList := mergeKLists(lists)
newList.Print()
}
// Insert 从链表节点尾部添加节点
func (ln *ListNode) Insert(val int) {
if ln == nil {
return
}
//创建一个新节点
newNode := &ListNode{Val: val}
cur := ln
//找到链表的末尾节点
for cur.Next != nil {
cur = cur.Next
}
//末尾节点的next指针域连接新节点
cur.Next = newNode
}
// Print 从链表头结点开始打印链表的值
func (ln *ListNode) Print() {
if ln == nil {
return
}
cur := ln
//遍历每一个节点
for cur != nil {
fmt.Print(cur.Val, "\t")
cur = cur.Next //更改指针变量的指向
}
fmt.Println()
}
//TODO： golang heap的使用：https://golang.google.cn/pkg/container/heap/如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解。
Python版本： [哔哩哔哩_bilibili
“哔哩哔哩_bilibili”)Java版本： [数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili
数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
“数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili”)Golang版本： [哔哩哔哩_bilibili
“哔哩哔哩_bilibili”)
4.小结
本题可以通过小顶堆完成，具体步骤为：
- 定义（引用）小顶堆；
- 每个链表的第一个节点放入堆中；
- 从堆中取出元素（取出的元素为节点值最小的），构成新的链表；
- 返回新链表的头节点。
难点在于小顶堆的应用。
更多算法视频讲解，你可以从以下地址找到：
Python编码实现： [数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili
数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
“数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili”)Java编码实现： [数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili
数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
“数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili”)Golang编码实现： [数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili
数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
“数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili”)
对于链表的相关操作，我们总结了一套【可视化+图解】方法，依据此方法来解决链表相关问题，链表操作变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句 ：山重水复疑无路，柳暗花明又一村。