「LeetCode每日一题」—— 23. 合并K个排序链表
23. 合并K个排序链表
链接:https://leetcode-cn.com/problems/merge-k-sorted-lists/
难度:中等
题目
点击原文链接跳转查看题目
思路
看到这个题目,想起了合并2个排序链表那个题,这个只是升级到了K个链表。
其实也参考2个链表的做法,分治合并,直到所有被合并。这里我们还可以更暴力,借助其他的数据结构,保证返回的链表是有序的就行。
第一,把所有的值加入数组中,然后排序,最后创建一个新链表。代码见暴力方案。
第二,可以创建一个小根堆,全部入堆,后面不断弹出来创建新链表。代码见堆排序。这里其实可以优化,把链表的头节点入堆即可,类似于排队有K排,但是只有一个售票员的情况。 这种情况下,售票员处理一个最小的,后面的就跟上。
方案代码
暴力方案:
# Definition for singly-linked list.
#class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
nodes = []
head = p = ListNode(0)
for l in lists:
while l:
nodes.append(l.val)
l = l.next
for x in sorted(nodes):
p.next = ListNode(x)
p = p.next
return head.next
堆排序:
# Definition for singly-linked list.
#class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
import heapq
class Solution(object):
def mergeKLists(self, lists):
head = p = ListNode(0)
heap = []
for l in lists:
while l:
heapq.heappush(heap, l.val)
l = l.next
while heap:
x = heappop(heap)
p.next = ListNode(x)
p = p.next
p.next = None
return head.next
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/354.html
您必须登录才能发表评论。