1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「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