写点什么

架构师训练营 - 第八周 - 作业

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

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

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



public Node mergeList(Node head1, Node head2) {
if (head1 == null || head2 == null) {
System.out.println("没有公共节点");
return null;
}
Node longNode;
Node shortNode;
int gapCount = 0;
int head1Length = getLength(head1);
int head2Length = getLength(head2);

if (head1Length > head2Length) {
longNode = head1;
shortNode = head2;
gapCount = head1Length - head2Length;
} else {
longNode = head2;
shortNode = head1;
gapCount = head2Length - head1Length;
}

for (int i = 0; i <gapCount; i++) {
longNode = longNode.next;
}
while (longNode != null && shortNode != null && longNode != shortNode) {
System.out.println("long---"+longNode.data);
System.out.println("short----"+shortNode.data);
longNode = longNode.next;
shortNode = shortNode.next;
if(longNode.data==shortNode.data){
head=longNode;
System.out.println("第一个公共节点是"+head.data);
return head;
}
}
return longNode;
}



用户头像

桔子

关注

还未添加个人签名 2018.11.15 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
请添加“极客大学架构师训练营标签”,便于分类~
2020 年 08 月 03 日 14:27
回复
没有更多了
架构师训练营 - 第八周 - 作业