写点什么

课后作业 -week08

用户头像
小叶
关注
发布于: 2020 年 07 月 29 日

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。



public Node getMergeNode(Node m,Node n){
//分别遍历m,n的链表,判端m和n里是否有元素相等
if(m == null && n == null) return null;
Node nodeA = m;
Node nodeB = n;
while(nodeA != nodeB){
nodeA = nodeA == null ? nodeB : nodeA.next();
nodeB = nodeB == null ? nodeA : nodeB.next();
}
return nodeA;
}



算法分别遍历了m,n,时间复杂度O(m+n) 记为O(n);额外申请了两个Node对象,空间复杂度为O(1)

用户头像

小叶

关注

还未添加个人签名 2018.10.21 加入

还未添加个人简介

评论

发布
暂无评论
课后作业-week08