[23][困难][堆] 合并K个排序链表

题目描述

23. 合并K个排序链表

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

示例:

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

解题思路

归并排序的基本思路, 配合堆结构实现.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        h = []
        num_links = len(lists)
        count = 0
        for i in range(num_links):
            if lists[i]:
                heapq.heappush(h, (lists[i].val, count, lists[i]))  # count的加入, 是为了避免Node节点参与比较, 引起报错
                count += 1

        cur = dummy_head = ListNode(0)  # 哨兵
        while h:
            _, _, node = heapq.heappop(h)
            cur.next = node
            cur = cur.next

            next_node = node.next
            if next_node is not None:
                heapq.heappush(h, (next_node.val, count, next_node))
                count += 1

        return dummy_head.next

相关题目

• [378][中等][堆][二分] 有序矩阵中第K小的元素