23. 合并 K 个升序链表 - 力扣(LeetCode)

基础知识要求：

Java：方法、while循环、for循环、PriorityQueue类、if判断

Python： 方法、while循环、for循环、heapq 模块、if判断

数据结构:队列 

题目： 

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• 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

思路解析：

对于合并多个已排序的列表或链表，一种常见的算法是使用最小堆（Min Heap）。在这个问题中，我们可以利用Python的heapq模块来实现最小堆。

Python的heapq模块不了解的，可以看一下我的这篇文章 Python 中的 heapq 模块简介

1. 初始化:
   • 创建一个虚拟头节点dummy，它的作用是简化链表的操作，因为我们可以直接操作dummy.next来构建结果链表，而不需要担心头节点为空的情况。
   • 创建一个指针p，指向dummy，它将用于遍历并构建结果链表。
   • 创建一个空的最小堆heap，用于存储待合并链表中的节点和它们的值。
2. 构建最小堆:
   • 遍历所有输入的链表lists。
   • 对于每个链表，如果链表不为空，将其头节点的值和节点本身作为一个元组(val, node)加入最小堆中。这里，我们利用节点的值val作为堆排序的优先级。
3. 合并链表:
   • 当最小堆不为空时，执行以下步骤：
     • 从堆中弹出具有最小值的节点，即当前所有链表中的最小节点。
     • 将这个节点添加到结果链表中，即设置p.next = node，并移动指针p到下一个位置。
     • 如果弹出的节点有下一个节点（即node.next不为空），将这个节点的下一个节点和它的值作为一个新的元组(node.next.val, node.next)加入最小堆中。
4. 返回结果:
   • 返回虚拟头节点的下一个节点dummy.next，这就是合并后的排序链表的头节点。

Java代码示例：

import java.util.PriorityQueue;  
  
class ListNode {  
    int val;  
    ListNode next;  
    ListNode(int x) { val = x; }  
}  
  
public class Solution {  
    public ListNode mergeKLists(ListNode[] lists) {  
        // 创建一个虚拟头节点  
        ListNode dummy = new ListNode(0);  
        ListNode p = dummy;  
          
        // 创建一个优先队列，按照节点的值排序  
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);  
          
        // 将所有链表的头节点加入优先队列  
        for (ListNode head : lists) {  
            if (head != null) {  
                pq.offer(head);  
            }  
        }  
          
        // 从优先队列中取出最小节点，直到队列为空  
        while (!pq.isEmpty()) {  
            ListNode node = pq.poll();  
            p.next = node;  
            p = p.next;  
              
            // 如果当前节点的下一个节点不为空，则加入优先队列  
            if (node.next != null) {  
                pq.offer(node.next);  
            }  
        }  
          
        // 返回结果链表的头节点（虚拟头节点的下一个节点）  
        return dummy.next;  
    }  
}

Python代码示例：

import heapq  
  
class ListNode:  
    def __init__(self, val=0, next=None):  
        self.val = val  # 节点的值  
        self.next = next  # 指向下一个节点的指针  
  
def mergeKLists(lists):  
    # 创建一个虚拟头节点，这样可以避免处理头节点为空的情况  
    dummy = ListNode(0)    
    p = dummy  # p用于遍历合并后的链表  
  
    # 创建一个最小堆，用于存储(节点值, 节点)对，这样我们可以根据节点值来排序  
    heap = []    
  
    # 遍历所有输入的链表，将非空链表的头节点加入最小堆  
    for lst in lists:    
        if lst:  # 如果链表不为空  
            heapq.heappush(heap, (lst.val, lst))  # 将节点的值和节点作为一个元组加入堆  
  
    # 当堆不为空时，继续合并链表  
    while heap:  
        # 弹出堆顶元素（即当前所有节点中的最小值节点）  
        val, node = heapq.heappop(heap)    
        # 将该节点连接到结果链表的末尾  
        p.next = node    
        p = p.next  # 移动指针到下一个位置  
  
        # 如果当前节点的下一个节点不为空，将其加入最小堆  
        if node.next:    
            heapq.heappush(heap, (node.next.val, node.next))    
  
    # 返回合并后链表的头节点（虚拟头节点的下一个节点）  
    return dummy.next  
  
# 示例：创建三个链表并合并它们  
lists = [  
    ListNode(1, ListNode(4, ListNode(5))),  # 链表1: 1->4->5  
    ListNode(1, ListNode(3, ListNode(4))),  # 链表2: 1->3->4  
    ListNode(2, ListNode(6))  # 链表3: 2->6  
]  
  
# 调用mergeKLists函数合并链表  
merged_list = mergeKLists(lists)  
  
# 打印合并后的链表  
current = merged_list  
while current:  
    print(current.val, end='->')  # 打印当前节点的值，并在末尾添加"->"  
    current = current.next  # 移动到下一个节点  
print('None')  # 表示链表结束