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

「LeetCode每日一题」—— 23. 合并K个排序链表

flypython • • leetcode题解

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

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 25/04/2020 11:05
下一篇 » 27/04/2020 11:07

相关推荐