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')  # 表示链表结束

相关推荐

  1. 23. 合并 K 升序 - (LeetCode)

    2024-05-14 08:10:12       5 阅读
  2. 刷题练习】23. 合并 K 升序

    2024-05-14 08:10:12       29 阅读
  3. LeetCode-23. 合并 K 升序

    2024-05-14 08:10:12       24 阅读
  4. LeetCode-23 合并 K 升序

    2024-05-14 08:10:12       34 阅读
  5. LeetCode 23 合并 K 升序

    2024-05-14 08:10:12       30 阅读
  6. LeetCode23.合并K升序

    2024-05-14 08:10:12       16 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-14 08:10:12       2 阅读
  2. QT--气泡框的实现

    2024-05-14 08:10:12       3 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-14 08:10:12       2 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-14 08:10:12       2 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-14 08:10:12       3 阅读
  6. C 语言设计模式(结构型)

    2024-05-14 08:10:12       2 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-14 08:10:12       2 阅读
  8. kafka防止消息丢失配置

    2024-05-14 08:10:12       3 阅读

热门阅读

  1. 【设计模式】桥接模式-学习记录

    2024-05-14 08:10:12       4 阅读
  2. 量子计算入门:原理与编程

    2024-05-14 08:10:12       2 阅读
  3. MySQL和MongoDB区别

    2024-05-14 08:10:12       3 阅读
  4. k8s 配置管理

    2024-05-14 08:10:12       3 阅读
  5. Redis 5.0 Stream数据结构深入分析

    2024-05-14 08:10:12       4 阅读
  6. 力扣:93. 复原 IP 地址

    2024-05-14 08:10:12       5 阅读
  7. 数据库和Redis数据不一致的问题

    2024-05-14 08:10:12       3 阅读
  8. Rust 语言不支持 goto 语句

    2024-05-14 08:10:12       6 阅读
  9. ubuntu 24.04 devilspie 报错解决

    2024-05-14 08:10:12       4 阅读
  10. CircleCI的原理及应用详解(二)

    2024-05-14 08:10:12       3 阅读
  11. 10、Go Gin 连接Redis以及Cookie&Session

    2024-05-14 08:10:12       4 阅读
  12. 使用frp通过http访问内网web服务

    2024-05-14 08:10:12       3 阅读