# 23. Merge k Sorted Lists 合并K个升序链表

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：合并，链表，单链表，题解，leetcode, 力扣，Python, C++, Java

## # 题目描述：

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

``````Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
``````

## # 解题方法

### # 方法一：每次遍历最小值（TLE）

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

class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
while True:
curIndex = -1
for i, llist in enumerate(lists):
if llist and llist.val < curHead.val:
curIndex = i
break
``````

### # 方法二：小根堆保存值和索引

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

class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
heap = []
heapq.heapify(heap)
[heapq.heappush(heap, (l.val, i)) for i, l in enumerate(lists) if l]
while heap:
curVal, curIndex = heapq.heappop(heap)
``````

### # 方法三：小根堆保存值和节点

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

class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
heap = []
heapq.heapify(heap)
[heapq.heappush(heap, (l.val, l)) for i, l in enumerate(lists) if l]
while heap: