23. 合并K个排序链表

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

示例:

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

思路--顺序合并

：用一个变量 ans 来维护已经合并的链表，第 i 次循环把第 i个链表和 ans 合并，答案保存到 ans 中。

python3解法--顺序合并

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def mergeTwoLists(ListNode1, ListNode2):
            if not ListNode1: return ListNode2
            if not ListNode2: return ListNode1
            mergedNode = ListNode(0)
            curNode = mergedNode
            while ListNode1 and ListNode2:
                if ListNode1.val < ListNode2.val:
                    curNode.next = ListNode1
                    ListNode1 = ListNode1.next
                else:
                    curNode.next = ListNode2
                    ListNode2 = ListNode2.next
                curNode = curNode.next
            curNode.next = ListNode1 if ListNode1 else ListNode2
            return mergedNode.next

        ans = None
        for node in lists:
            ans = mergeTwoLists(ans, node)
        return ans

思路--分治

以下图为例：
开始数组的规模是6，我们找到中间点，将起一分为二，然后再拆分，直到不能再拆分(规模为1时)时便返回。
之后开始合并，合并的代码借用了合并两个排序链表的代码。
当两个规模最小的链表合并完后，其规模就变大了，然后不断重复这个合并过程，直到最终得到一个有序的链表。

image.png

python3解法--分治

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

class Solution:
    def mergeTwoLists(self, ListNode1, ListNode2):
            if not ListNode1: return ListNode2
            if not ListNode2: return ListNode1
            mergedNode = ListNode(0)
            curNode = mergedNode
            while ListNode1 and ListNode2:
                if ListNode1.val < ListNode2.val:
                    curNode.next = ListNode1
                    ListNode1 = ListNode1.next
                else:
                    curNode.next = ListNode2
                    ListNode2 = ListNode2.next
                curNode = curNode.next
            curNode.next = ListNode1 if ListNode1 else ListNode2
            return mergedNode.next

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        length = len(lists)
        # 边界情况
        if not lists or length < 1: return None
        if length == 1:
            return lists[0]
        # 分治
        mid = length // 2
        return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:length]))

思路-- 优先队列（heap）

python3解法-- 优先队列（heap）

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 存储所有的链表节点的值
        heap = []
        # 遍历链表，使用小顶堆排序数组
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        head = ListNode(None)
        curNode = head
        # 遍历数组，依次弹出最小的值，并创建新的节点存储
        while heap:
            curNode.next = ListNode(heapq.heappop(heap))
            curNode = curNode.next
        return head.next

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。