架构师训练营 - 作业 8

用户头像
进击的炮灰
关注
发布于: 2020 年 07 月 29 日
架构师训练营 - 作业 8

第一题:



两个单链表拥有同一个元素,也就是说这个同一个元素的子元素是一样的,那么他们后面的节点都是一致的,可以确定的是尾节点一定是一样的,这两个单链表就像  Y 一样。 现在要确定的是第一个一样的节点(也就是交点)的位置。

若m=n,即长度相等, 那么我们只需要同时遍历两个链表,然后判断是否相等即可:

while (element_a.next != null && element_b.next != null) {

curA = element_a.next;

curB = element_b.next;

if(curA  == curB) {

//当前位置即为第一个交点

break;

}

element_a=curA;

element_b=curB;

}

若m!=n, 两个链表长度不相等, 它们重叠的部分一定是在链表的后端,而两个链表长度不一致,假设链表a比链表b长,那么长链表a前面多出的元素不可能会存在交点的,那么我们可以得到两个链表的个数差为 m-n,先从a链表中遍历 m-n个元素 ,然后接下来同时遍历a 和b 链表, 和 m=n的情况一样。

if (m>n){

for (int i=0;i<m-n;i++)

element_a = element_a.next;

}

该算法时间复杂度为O(max(m,n)), 空间复杂度为O(1)。



用户头像

进击的炮灰

关注

还未添加个人签名 2020.05.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 作业 8