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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#

def MergeTwoLists(pHead1: ListNode, pHead2: ListNode) -> ListNode:
    flag = ListNode(-1)
    result = None
    # 如果两个链表都是空链表。
    if (not pHead1) and (not pHead2):
        return pHead1
    # 选择小的元素放入结果链表。
    while pHead1 and pHead2:
        if pHead1.val < pHead2.val:
            if result is None:
                result = pHead1
                # 记录结果链表的头节点。
                flag.next = result
                pHead1 = pHead1.next
            else:
                result.next = pHead1
                result = result.next
                pHead1 = pHead1.next
        else:
            if result is None:
                result = pHead2
                flag.next = result
                pHead2 = pHead2.next
            else:
                result.next = pHead2
                result = result.next
                pHead2 = pHead2.next
    # 当一个链表的元素已经全部访问，直接把另一个链表的剩余部分接入到结果链表。
    if pHead1:
        # 如果有一个链表是空链表，没有经过上面的循环过程，此处也需要记录结果链表的头节点。
        if result is None:
            result = pHead1
            # 记录结果链表的头节点。
            flag.next = result
        else:
            result.next = pHead1

    else:
        if result is None:
            result = pHead2
            flag.next = result
        else:
            result.next = pHead2

    return flag.next


class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # 每次合并两个链表，
        # 首先将第一个链表和第二个链表合并，然后再和第三个链表合并，直到所有链表都合并。
        if not lists:
            return None
        result_lst = lists[0]
        for lst in lists[1::]:
            result_lst = MergeTwoLists(result_lst, lst)
        
        return result_lst