侯瑞哲的博客

Ruizhe's Blog

0%

leetcode 23.合并K个排序链表

发表于 Valine：

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6

是工业界很常见的一种操作，比如分布式系统中、数据库中，我们有多个索引是有序的，且在多个小文件中存储，我们要合并成一个新的有序链表。我们可以有哪些想法呢。

最暴力的解法是，每次遍历所有链表，找到最小的链表头，将结果链表的下一个指针指向该链表头，然后链表头指向其下一个节点。

  • 时间复杂度：找最小的链表头O(k)，假设链表平均长度n，要找O(nk)次，总体是O(k^2n)的。
  • 空间复杂度：O(1)，不使用额外空间

对于我来说最直接的想法是，建一个dummy哨兵链表节点，用cur指针指向dummy，同时观察所有链表的头部元素，选出最小的一个，将cur.next指向这个链表头，这个链表如果next不为Null，就加入这个链表头的集合中，否则就不加入，然后令cur=cur.next。这样加入我们共有K个链表，那么我们的集合就是K这么大，这样插入一个元素，每次删除其中最小元素都很高效的数据结构是堆。

  • 总的时间复杂度就是O(k*n*logk)。因为我们一共要插入和删除K次。
  • 空间复杂度：O(K)，我们要使用一个K大小的堆。

另一种想法用分治的方法进行合并。我们

  • 将k个链表配对，将一对中的链表合并。
  • 第一轮合并以后，k个链表被合并成了k/2个链表，平均长度为2n/k，然后是k/4个链表，k/8个链表等等。
  • 重复这一过程，直到我们得到了最终的有序链表。

我们来分析一下复杂度：

  • 时间复杂度：我们知道合并两个有序链表，等于两个链表长度的和，所以是O(2n)，要合并k/2个，之后合并k/4个链表，合并时间复杂度是O(4n)，所以最终的时间复杂度还是O(n k log(k)) 。
  • 空间复杂度：我们归并要使用递归，递归的深度为logk，所以我们要使用O(logk)的栈空间。

示例代码

使用堆合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        # 这里的i为了排序
        heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
        heapq.heapify(heap)
        while heap:
            val, ind, l = heapq.heappop(heap)
            cur.next = l
            if l.next:
                l = l.next
                heapq.heappush(heap, (l.val, ind, l))
            cur = cur.next
        return dummy.next

分支合并

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
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return
        n = len(lists)
        return self.merge(lists, 0, n - 1)

    def merge(self, lists, l, r):
        if l >= r:
            return lists[l]
        mid = l + ((r - l) >> 1)
        l1 = self.merge(lists, l, mid)
        l2 = self.merge(lists, mid + 1, r)
        return self.mergeTwoLists(l1, l2)

    def mergeTwoLists(self, l1, l2):
        dummy = cur = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next