题解 | #合并k个已排序的链表#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param lists ListNode类一维数组
# @return ListNode类
#
class Solution:
    def Merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        phead = ListNode(-1)
        CUR = phead
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                cur = pHead1
                pHead1 = pHead1.next
            else:
                cur = pHead2
                pHead2 = pHead2.next
            CUR.next = cur
            CUR = CUR.next
        CUR.next = pHead1 if pHead1 else pHead2
        head = phead.next
        del phead
        return head

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # write code here
        if len(lists) == 0:
            return None
        elif len(lists) == 1:
            return lists[0]
        elif len(lists) == 2:
            return self.Merge(lists[0], lists[1])
        else:
            new_head = self.Merge(lists[0], lists[1])
            return self.mergeKLists([new_head] + lists[2:])