当前位置:网站首页>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
边栏推荐
- One of the general document service practice series
- zabbix监控系统邮件报警配置
- Valentine's Day is coming! Without 50W bride price, my girlfriend was forcibly dragged away...
- OKR vs. KPI 一次搞清楚这两大概念!
- Rhcsa day 3
- Distributed transaction management DTM: the little helper behind "buy buy buy"
- Rapidjson reading and writing JSON files
- Introduction to sap commerce cloud B2B organization function
- This monitoring system can monitor the turnover intention and fishing all, and the product page has 404 after the dispute appears
- JVM中堆概念
猜你喜欢
Handwritten easy version flexible JS and source code analysis
博客停更声明
神经网络入门(下)
MySQL中的文本处理函数整理,收藏速查
Write a thread pool by hand, and take you to learn the implementation principle of ThreadPoolExecutor thread pool
This monitoring system can monitor the turnover intention and fishing all, and the product page has 404 after the dispute appears
The idea of implementing charts chart view in all swiftui versions (1.0-4.0) was born
Zhanrui tankbang | jointly build, cooperate and win-win zhanrui core ecology
This article is enough for learning advanced mysql
墨者学院-Webmin未经身份验证的远程代码执行
随机推荐
The text box displays the word (prompt text) by default, and the text disappears after clicking.
Email alarm configuration of ZABBIX monitoring system
Activiti common operation data table relationship
Valentine's Day is coming! Without 50W bride price, my girlfriend was forcibly dragged away...
zabbix监控系统自定义监控内容
How to write a summary of the work to promote the implementation of OKR?
A real penetration test
ZABBIX 5.0 monitoring client
zabbix監控系統自定義監控內容
果果带你写链表,小学生看了都说好
Guoguo took you to write a linked list, and the primary school students said it was good after reading it
Leetcode (215) -- the kth largest element in the array
Docker install MySQL
弈柯莱生物冲刺科创板:年营收3.3亿 弘晖基金与淡马锡是股东
墨者学院-Webmin未经身份验证的远程代码执行
Literature collation and thesis reading methods
Detailed introduction to the big changes of Xcode 14
Relations courantes de la fiche de données d'exploitation pour les activités
21 examples of strategic goals to promote the rapid development of your company
Xcode 14之大变化详细介绍