C/C++练习题之合并k个已排序的链表

这是一道经典的算法题，解决方法可以使用分治或者堆。

题目描述

合并k个已排序的链表并将其作为一个已排序的链表返回。分析并描述其时间复杂度和空间复杂度。

示例1：

输入：[[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表可视化如下：

  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

将它们合并成一个有序链表后，变成了如下列表：

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

解题思路

分治法

先将k个链表分组，两两配对进行合并，得到k/2个链表，然后再以两两配对进行合并，直到得到一个有序链表。

这里使用递归的方式实现，时间复杂度为$O(NlogK)$，空间复杂度为$O(1)$。其中$N$为链表中元素的总数，$K$为链表的数目。

堆

将每个链表的第一个元素加入一个小根堆中，弹出堆顶的元素，并将该节点的下一个节点加入堆中，重复该过程直到所有链表连接成一个有序链表。

时间复杂度为$O(NlogK)$，空间复杂度取决于堆的大小，最多不会超过$O(K)$。

代码实现

分治法

def mergeKLists(lists):
    if not lists:
        return None
    if len(lists) == 1:
        return lists[0]
    mid = len(lists) // 2
    left = mergeKLists(lists[:mid])
    right = mergeKLists(lists[mid:])
    return mergeTwoLists(left, right)

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    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

堆

import heapq
def mergeKLists(lists):
    dummy = ListNode(0)
    cur = dummy
    heap = []
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, node))
    while heap:
        cur.next = heapq.heappop(heap)[1]
        cur = cur.next
        if cur.next:
            heapq.heappush(heap, (cur.next.val, cur.next))
    return dummy.next

以上是两种不同解法的Python实现，其中ListNode是链表节点的定义。