架构师训练营 - 作业 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)。