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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        length = len(lists) #获取列表长度
        listnew = [] #生成一个空列表
        if length < 1 : #如果长度为0，返回空
            return None
        if length == 1: #如果长度为1，返回第一个元素
            return lists[0]
        for i in range(0,length,2):#依次从列表中取两个链表进行比较并合并，生成一个新的链表，并添加到空列表中
            pre = cur = ListNode(0) #生成一个空链表，用于缓存两两链表合并后的链表
            if i != length - 1:#如果不是最后一个链表进行如下合并操作
                while lists[i] and lists[i + 1]:#如果第i个和第i+1个链表不为空，进行如下合并操作
                    if lists[i].val < lists[i + 1].val:#如果前一个链表的数小于第二个链表
                        cur.next = lists[i]#将list[i]挂接到cur上
                        lists[i] = lists[i].next#移动list【i】的指针位置
                    else:#如果前一个链表的值不小于第二个链表的值
                        cur.next = lists[i + 1]#将第二个链表当前指针挂接到cur上
                        lists[i + 1] = lists[i + 1].next#移动指针位置
                    cur = cur.next #移动cur当前指针
                cur.next = lists[i] or lists[i + 1]#上面循环完成后，两个链表必有一个为空，一个不为空，不为空的指针位置在最后一个数，将指针挂接到cur
                listnew.append(pre.next)#将合并完成的链表添加到listnew
            else:#如果当前是列表的最后一个链表，因为没有可以比较的链表，直接将该链表添加到listnew
                listnew.append(lists[i])
        return Solution.mergeKLists(self,listnew) #递归调用函数，入参为上面生成的新的列表，最终返回结果为列表的第0号链表。