当前位置:网站首页>Leetcode 23. 合并K个升序链表
Leetcode 23. 合并K个升序链表
2022-07-04 07:41:00 【von Libniz】
题目链接:https://leetcode.cn/problems/merge-k-sorted-lists/
题目描述
给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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路归并的扩展,而数组k路归并存在三种解法(假设k路数组的所有元素数为n):
(1)k路数组拷贝至同一数组,再统一排序
(2)k路数组进行k次归并
(3)使用最小堆,依次从k个数组中找到最小值,重复n次
而这题把数组换成了链表,那使用第三种方法是比较合适的。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
k = len(lists)
dummy = ListNode(val=-1)
tail = dummy
heap = []
# put each list head to min heap
for i, node in enumerate(lists):
if node is not None:
heap.append((node.val, i, node)) # 当val相同通过link_index:i比较
heapq.heapify(heap)
# find min node n times
while len(heap) > 0:
_, idx, cur_node = heapq.heappop(heap)
tail.next = cur_node
tail = cur_node
if cur_node.next is not None:
heapq.heappush(heap, (cur_node.next.val, idx, cur_node.next))
return dummy.next
边栏推荐
- L1-024 the day after tomorrow (5 points)
- Application of isnull in database query
- ZABBIX monitoring system deployment
- [FreeRTOS] FreeRTOS learning notes (7) - handwritten FreeRTOS two-way linked list / source code analysis
- SQL注入测试工具之Sqli-labs下载安装重置数据库报错解决办法之一(#0{main}thrown in D:\Software\phpstudy_pro\WWW\sqli-labs-……)
- How to send mail with Jianmu Ci
- Système de surveillance zabbix contenu de surveillance personnalisé
- Book list | as the technical support Party of the Winter Olympics, Alibaba cloud's technology is written in these books!
- 神经网络入门(下)
- It's healthy to drink medicinal wine like this. Are you drinking it right
猜你喜欢
Node foundation ~ node operation
弈柯莱生物冲刺科创板:年营收3.3亿 弘晖基金与淡马锡是股东
线性代数1.1
[network security] what is emergency response? What indicators should you pay attention to in emergency response?
There is no Chinese prompt below when inputting text in win10 Microsoft Pinyin input method
tornado项目之路由装饰器
BUUCTF(4)
[C language] open the door of C
论文学习——基于极值点特征的时间序列相似性查询方法
Handwritten easy version flexible JS and source code analysis
随机推荐
Introduction to rce in attack and defense world
Google's official response: we have not given up tensorflow and will develop side by side with Jax in the future
How to buy financial products in 2022?
tornado之目录
Write a thread pool by hand, and take you to learn the implementation principle of ThreadPoolExecutor thread pool
ZABBIX monitoring system deployment
MySQL 数据库 - 函数 约束 多表查询 事务
博客停更声明
时序数据库 InfluxDB 2.2 初探
tornado项目之路由装饰器
Zhanrui tankbang | jointly build, cooperate and win-win zhanrui core ecology
zabbix 5.0监控客户端
[Android reverse] function interception (use cache_flush system function to refresh CPU cache | refresh CPU cache disadvantages | recommended time for function interception)
Système de surveillance zabbix contenu de surveillance personnalisé
Transition technology from IPv4 to IPv6
User login function: simple but difficult
How does dataframe calculate the average value of each row as another column
The idea of implementing charts chart view in all swiftui versions (1.0-4.0) was born
Go learning notes - constants
[Flink] temporal semantics and watermark