> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/niu-ke-0051-kun-nan-he-bingkge-yi-pai-xu-de-lian-biao.md).

# 合并k个已排序的链表

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%A0%86/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/03/pages/R5NyOzkn3qAZy7wCx1pS#堆优先队列)

> [合并k个已排序的链表\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6)

**问题简述**

```
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
```

**思路：堆/优先队列**

<details>

<summary><strong>写法1：不重载运算符，利用 tuple 排序</strong></summary>

```python
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        
        import heapq
        
        h = []
        cnt = 0  # 一个自增变量，避免直接对 node 排序
        
        # init
        for node in lists:
            if node:
                heapq.heappush(h, (node.val, cnt, node))
                cnt += 1
        
        cur = dummy = ListNode(0)
        while h:
            _, _, node = heapq.heappop(h)
            cur.next = node
            cur = cur.next
            if node.next:
                node = node.next
                heapq.heappush(h, (node.val, cnt, node))
                cnt += 1
        
        return dummy.next
```

</details>

<details>

<summary><strong>写法2：重载运算符</strong></summary>

```python
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        
        import heapq
        
        h = []
        cnt = 0
        
        # 重载运算符
        def lt(a, b):
            return a.val < b.val
        ListNode.__lt__ = lt

        # 下面的写法也可以，但是不推荐，因为 lambda 表达式是不支持序列化的
        # ListNode.__lt__ = lambda a, b: a.val < b.val
        
        # init
        for node in lists:
            if node:
                heapq.heappush(h, node)
        
        cur = dummy = ListNode(0)
        while h:
            node = heapq.heappop(h)
            cur.next = node
            cur = cur.next
            if node.next:
                node = node.next
                heapq.heappush(h, node)
        
        return dummy.next
```

</details>