第八周作业 - 命题作业

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

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

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





//判断链表是否合并
boolean hasMergeNode(Node linkNode1,Node linkNode2){
Node node1 = linkNode1;
Node node2 = linkNode2;
while(node1.next() != null){
node1 = node1.next();
}
while(node2.next() != null){
node2 = node2.next();
}
if(node1 == node2){
return true;
}
return false;
}

//找到两个链表中合并的元素
Node getMergeNode(Node linkNode1,Node linkNode2){
Node node1 = linkNode1;
Node node2 = linkNode2;
int lenght1 = 0;
int length2 = 0;
while(node1.next() != null){
node1 = node1.next();
lenght1++;
}
while(node2.next() != null){
node2 = node2.next();
length2++;
}
if(lenght1 > lenght2){
node1 = linkNode1;
node2 = linkNode2;
}else{
node1 = linkNode2;
node2 = linkNode1;
}
int lenght = abs(lenght1 - lenght2);
for(int i = 0; i < lenght; i++){
node1 = node1.next();
}
while(node1 != node2){
node1 = node1.next();
node2 = node2.next();
}
return node1;
}

时间复杂度:O(n)



用户头像

molly

关注

还未添加个人签名 2017.12.14 加入

还未添加个人简介

评论

发布
暂无评论
第八周作业 - 命题作业