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

用户头像
狂奔嘀兔纸
关注
发布于: 刚刚

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

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





算法思想:利用链表的长度差,先获取两个链表最短的长度,然后只遍历同等长度的链表来获取公共节点的信息。

时间复杂度:O(M+N)

空间复杂度:O(1)



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;
}



发布于: 刚刚 阅读数: 3
用户头像

狂奔嘀兔纸

关注

还未添加个人签名 2018.04.28 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营-第八周-作业