> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/lian-biao/23-he-bingkge-pai-xu-lian-biao.md).

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

## 题目描述

[23. 合并K个排序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/)

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

示例:

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

## 解题思路

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

```python
# 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小的元素](broken://pages/-McTyQwggZw_TCjAPdZi)