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

合并k个已排序的链表

http://www.nowcoder.com/questionTerminal/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

思路:
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

全部评论
啊!有这个思路但是面试没写出来。哭
点赞 回复 分享
发布于 2021-01-28 23:43

相关推荐

每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
买蜜雪也用卷:我觉得应该没有哪个人敢说自己熟练使用git,代码分支一复杂还是得慢慢寻思一下的,不过基本的拉代码提交代码还有分支什么的是应该会
点赞 评论 收藏
分享
明天不下雨了:让我们大声的说出来:以前的未来就是现在
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务