23.合并k个升序链表

思路：

1. 如何合并2个升序链表 递归法：l1的值小于l2，则l1的下一个节点为l1剩下的节点与l2节点合并的结果；反之，l2的下一个节点为l2剩下的节点和l1合并的结果。
2. 对k个链表，将其中2个链表合并为1个，直到所有链表合为了1个。

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        if lists == [[]]:
            return []
        #递归合并2个升序链表
        def mergeTwoLists(list1,list2):
            if list1 == None:
                return list2
            elif list2 == None:
                return list1
            elif list1.val < list2.val:
                list1.next = mergeTwoLists(list1.next,list2)
                return list1
            else:
                list2.next = mergeTwoLists(list2.next,list1)
                return list2
        while len(lists) > 1:
            list1 = lists.pop()
            list2 = lists.pop()
            merged = mergeTwoLists(list1,list2)
            lists.append(merged)
        return lists[0]