合并 k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度

思路：
1比较两个链表得到新的有序链表；
2比较新得到链表和第三个链表，以此类推；

本来想着用递归实现，但线上的IDE性能问题直接没有通过，可能是空间复杂度太大了，后面改用循环的方法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class Solution:
    def mergeKLists(self , lists ):
        # write code here
        res=None
        for ln in lists:
            res=self.mergeTwoLists(res, ln)
        return res
    def mergeTwoLists(self,l1,l2):
        #递归比较两个链表，直到遍历完其中一个,空间复杂度太大
        # if not l1 or not l2:
        #     return l1 if not l2 else l2
        # elif l1.val<l2.val:
        #     l1.next=self.mergeTwoLists(l1.next, l2)
        #     return l1
        # else:
        #     l2.next=self.mergeTwoLists(l1, l2.next)
        #     return l2

       #循环
        head=res=ListNode(0)
        while l1 or l2:
            if not l1 or not l2:
                head.next=l1 if not l2 else l2
                break

            elif l1.val<l2.val:
                head.next=l1
                head,l1=head.next,l1.next

            else:
                head.next=l2
                head,l2=head.next,l2.next
        return res.next