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

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 和合并两个链表的思路是一样的，只不过这次要比较的是多个链表的最小值而已
# 将链表当前头节点和当前头节点的 val 值分别保存在两个列表中，并且一一对应
# 通过查找 val 列表找到最小节点，并得到下标
# 通过下标保存最小节点，并将最小节点右移一位，每当一个链表遍历结束，就将该链表删除
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        nodeList = []
        valueList = []

        for i in lists:
            if i == None:
                continue
            nodeList.append(i)
            valueList.append(i.val)
        
        if len(nodeList) == 0:
            return None
        elif len(nodeList) == 1:
            return nodeList[0]

        m = min(valueList)
        i = valueList.index(m)
        head = nodeList[i]
        nodeList[i] = nodeList[i].next
        if nodeList[i] == None:
            nodeList.pop(i)
            valueList.pop(i)
        else:
            valueList[i] = nodeList[i].val
        node = head

        

        while len(nodeList) > 1:
            m = min(valueList)
            i = valueList.index(m)
            head.next = nodeList[i]
            head = head.next
            nodeList[i] = nodeList[i].next
            if nodeList[i] == None:
                nodeList.pop(i)
                valueList.pop(i)
                continue
            
            valueList[i] = nodeList[i].val
        
        head.next = nodeList[0]
        return node