当前位置:网站首页>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
边栏推荐
- Introduction to neural network (Part 2)
- [Mori city] random talk on GIS data (I)
- Devops Practice Guide - reading notes (long text alarm)
- [untitled] notice on holding "2022 traditional fermented food and modern brewing technology"
- MYCAT middleware installation and use
- Activiti common operation data table relationship
- 墨者学院-phpMyAdmin后台文件包含分析溯源
- Zephyr Learning note 2, Scheduling
- There is no Chinese prompt below when inputting text in win10 Microsoft Pinyin input method
- Oceanbase is the leader in the magic quadrant of China's database in 2021
猜你喜欢
flask-sqlalchemy 循环引用
时序数据库 InfluxDB 2.2 初探
Unity opens the explorer from the inspector interface, selects and records the file path
Zephyr 学习笔记1,threads
Zabbix agent主动模式的实现
大厂技术专家:架构设计中常用的思维模型
BUUCTF(3)
Node foundation ~ node operation
In the era of low code development, is it still needed?
Implementation of ZABBIX agent active mode
随机推荐
Rapidjson reading and writing JSON files
Improve the accuracy of 3D reconstruction of complex scenes | segmentation of UAV Remote Sensing Images Based on paddleseg
The frost peel off the purple dragon scale, and the xiariba people will talk about database SQL optimization and the principle of indexing (primary / secondary / clustered / non clustered)
Introduction to rce in attack and defense world
Unity opens the explorer from the inspector interface, selects and records the file path
Linear algebra 1.1
Google's official response: we have not given up tensorflow and will develop side by side with Jax in the future
Would you like to go? Go! Don't hesitate if you like it
21 examples of strategic goals to promote the rapid development of your company
flask-sqlalchemy 循环引用
Literature collation and thesis reading methods
[real case] how to deal with the failure of message consumption?
论文学习——基于极值点特征的时间序列相似性查询方法
2022-021rts: from the second half of the year
Blue Bridge Cup Quick sort (code completion)
How to send mail with Jianmu Ci
真空介电常数和真空磁导率究竟是由什么决定的?为何会存在这两个物理量?
Preliminary study on temporal database incluxdb 2.2
Is l1-029 too fat (5 points)
Directory of tornado