你变成我,我变成你,我们便相遇了。
原题
这是一道链表的题,原题如下:
给定两个(单向)链表,判定它们是否相交并返回交点。请注意相交的定义基于节点的引用,而不是基于节点的值。换句话说,如果一个链表的第 k 个节点与另一个链表的第 j 个节点是同一节点(引用完全相同),则这两个链表相交。
示例 1:
1 | 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 |
示例 2:
1 | 输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 |
示例 3:
1 | 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 |
注意:
如果两个链表没有交点,返回 null
。
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n)
时间复杂度,且仅用 O(1)
内存。
解题思路
你变成我,我变成你,我们便相遇了。
那么为什么能相遇呢?
- 设长链表 A 长度为 LA,短链表长度 LB;
- 由于速度相同,则在长链表 A 走完 LA 长度时,短链表 B 已经反过头在 A 上走了 LA-LB 的长度,剩余要走的长度为 LA-(LA-LB) = LB;
- 之后长链表 A 要反过头在 B 上走,剩余要走的长度也是 LB;
- 也就是说目前两个链表“对齐”了。因此,接下来遇到的第一个相同节点便是两个链表的交点。
那如果两个链表不存在交点呢?
答:这样的话第 4 步就会一直执行到两个链表的末尾,la,lb 都为 null,也会跳出循环,返回 null。
代码
1 | /** |
评论