Fork me on GitHub

23 - 合并K个元素的有序链表

发表于 | 分类于

题目描述

审题：
首先吧，这个题目我就没看懂，合并有序链表并返回有序链表，excuse me？？
然后吧，看了一下输入输出type，索德斯呢~~ k个链表都是有序的，合并成一个/摊手
最后吧，想起来之前做过一个合并俩有序链表的,传送门。当时最简洁的方法是使用了递归，现在是K个链表的话，一个个连铁定超时没得跑的。
怎么办呢，偷偷瞟一眼相关话题，有堆和分治算法。哎，第一反应就是把算法书翻出来再学一遍，虽然前面已经几乎两遍了，算法助教说的果然没错，这本书是值得花时间的。

分治算法

  1. 对半划分直到只有一个或两个链表；
  2. 使用合并两个有序链表的方法合并。
    以4链表为例：
    1、3合并，合并结果放到1的位置；
    2、4合并，合并结果放到2的位置；
    再把1、2合并（相当于原来的13 和 24合并）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution:
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            l = len(lists)
            if l == 0:
                return None
            while l > 1:
                k = (l + 1) // 2
                for i in range(l // 2):
                    lists[i] = mergeTwoLists(lists[i], lists[i + k])
                l = k
            return lists[0]

        def mergeTwoLists(self, l1, l2):
            if not l1:
                return l2
            elif not l2:
                return l1
            else:
                if l1.val < l2.val:
                    l1.next = self.mergeTwoLists(l1.next, l2)
                    return l1
                else:
                    l2.next = self.mergeTwoLists(l1, l2.next)
                    return l2

递归深度超限了orz,Python中默认的最大递归深度是989，当尝试递归第990时便出现递归深度超限的错误:

虽然可以手动设置递归调用深度：

1
2
import sys
sys.setrecursionlimit(10000000)

但是我不要，我！不！要!/傲娇脸
应该是合并两个链表也是递归，所以就好多好多递归所以超了吧。
把合并两个数组改一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def mergeTwoLists(self, l1, l2):
        head = ListNode(0)
        res = head
        while l1 and l2:
            if l1.val < l2.val:
                res.next = l1
                l1 = l1.next
            else:
                res.next = l2
                l2 = l2.next
            res = res.next
        if l1:
            res.next = l1
        elif l2:
            res.next = l2
        return head.next

果然通过了哗哈哈哈哈哈哈哈哈哈哈哈✧*｡٩(ˊᗜˋ)و✧｡

最小堆

  1. 把k个链表的首元素加入最小堆中，使其升序排列；
  2. 每次取出堆顶元素（最小）加入结果链表，然后将其后那个元素加入最小堆；
  3. 直到把堆取空了，结果链表就合并完成了。

but…python没有实现堆这样的数据结构呀，计几构建吧。哈哈哈，下次吧嘻嘻

1
2