合并 K 个排序链表

合并 K 个排序链表

leetcode 38

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

示例:

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

分治法

使用和归并排序一样的分治算法。

每两个链表进行合并，逐层返回。既使用了分治法，也使用了递归。

# 分治法
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    return self.merge(lists, 0, len(lists) - 1)
 
def merge(self, lists, left, right):
    if left == right:
        return lists[left]
    if left < right:
        mid = left + right >> 1
        return self.mergeTwoList(self.merge(lists, left, mid), self.merge(lists, mid+1, right))
 
def mergeTwoList(self, l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = self.mergeTwoList(l1.next, l2)
        return l1
    l2.next = self.mergeTwoList(l1, l2.next)
    return l2

---

堆

方法一

第一种考虑是将所有元素放置到最小堆里，堆会自动调整顺序。

考虑优先队列中的元素不超过 $n$ 个，那么每次插入和删除的时间代价为 $O(\log n)$，所以整体时间复杂度是 $O(n \log n)$。$n$ 代表元素的总和。

空间复杂度是 $O(n)$。

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return
    queue = []
    cur = dummy = ListNode(0)
    for node in lists:
        while node:
            heapq.heappush(queue, (node.val, node))  # 需要 ListNode 构造加上 _lt_
            node = node.next
    while queue:
        _, cur.next = heapq.heappop(queue)
        cur = cur.next
    return dummy.next

我们设想在堆里放入：node.val, node，前者用于比较大小，后者直接用于链表的组装。

但是会出现：TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'错误。
原因是：堆元素可以为元组进行排序。元组在 heapq 里比较的机制是从元组首位 0 开始，即遇到相同，就比较元组下一位，比如 (1,2), (1,3)，前者比后者小。
这题刚好 node 值有重复的，同时 ListNode 无法被比较，所以可以解释编译器为什么报错。

解决方法是在类 ListNode 里面添加比较方法：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
    def __lt__(self, other):
        return self.val < other.val

__lt__ 是定义对象比较的 < 操作，当然你定义为 > 也没毛病。两个写一个就行。

    def __gt__(self, other):
        return self.val > other.val

不足之处：
就是相当于取出全部元素进行由大到小排序，然后进行链表的拼接，而排序的时间复杂度是 $O(n \log n)$，很明显这种方法并没有利用堆降低时间复杂度。

方法二：真正堆的使用

我们维护一个大小为 $k$ 的堆，堆由每个链表的首元素组成，每次堆弹出一个元素，就由该链表的下个结点进入。
如图所示：

# 假定已经定义了 ListNode 的比较方法
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return
    queue = []
    cur = dummy = ListNode(0)
    for node in lists:
        if node:
            heapq.heappush(queue, node)  # 同样需要 ListNode 构造加上 _lt_
 
    while queue:
        head = heapq.heappop(queue)
        cur.next = head
        cur = cur.next
        if head.next:
            heapq.heappush(queue, head.next)
    return dummy.next

若是没有定义结点的比较方法，我们可以将堆里面存入结点的值和链表所在的索引号。

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return
    queue = []
    cur = dummy = ListNode(0)
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(queue, (node.val, i))
  
    while queue:
        val, idx = heapq.heappop(queue)
        cur.next = ListNode(val)
        cur = cur.next
        if lists[idx].next:
            heapq.heappush(queue, (lists[idx].next.val, idx))
            lists[idx] = lists[idx].next  # lists[idx] 相当于指针，这点很有意思。
    return dummy.next

时间复杂度为 $O(n \log k)$，空间复杂度是 $O(k)$。

参考

四种解法+多图演示 23. 合并K个排序链表
合并 K 个排序链表
python c++ 优先队列(最小堆） O(n*logk)
合并K个排序链表

本文地址：https://blog.csdn.net/weixin_43932942/article/details/107101700