摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。
爱写Bug（ID：iCodeBugs）
编写一个程序，找到两个单链表相交的起始节点。
Write a program to find the node at which the intersection of two singly linked lists begins.
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：**
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Reference of the node with value = 2 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：**
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(_n_) 时间复杂度，且仅用 O(_1_) 内存。 相交链表
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
解题思路：注意：长链表比短链表多出的长度是无需比较的
刚开始我是想着直接从两个链表末尾向前遍历对比节点是否相等，后面才看到是单链表。但是依然有很多的解题方法：
哈希表：把一个链表的节点先存储在哈希表，遍历另一个节点并判断该节点地址是否在哈希表中出现过如果出现过，输出该节点。需要占用额外空间 O(n)。
如果按要求在 O(1) 空间复杂度解题，最容易想到的就是：遍历链表得到链表长度，计算双链表差值，长链表减去差值得到的剩下的链表与短链表长度相等，然后开始比较地址。，当遇到第一个节点地址相同时即为所求。
这个原理简单，但是代码太冗长了，我们来看另一种更优雅的解法，看图帮助理解：
定义两个指针curA、curB分别从链表A、B开始遍历链表，此时最先遇到空节点(到达末尾)的链表即为短链表。
curA、curB走过的长度均为LenA。
此时将curA指向链表 B (长链表)的头节点，curB 不变。两个指针开始第二段遍历，直到 curB 遇到空节点（长链表到达末尾）。
此时 curB 走完整个长链表，走的第二段长度就是差值 L。CurA 从长链表头节点开始，与 curB 同步，其走的第二段长度同样是差值 L。
此时 curA 在长链表 剩余未遍历的节点长度是：LenB - L = LenA
此时将 curB 指向链表A的头节点，即将遍历链表A 的长度为 LenA ，则curA、curB剩余即将遍历的长度即为原本需要比较的长度。
开始第三段遍历，遇到第一个相同节点时返回即可。
代码：Java：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode curA = headA;
ListNode curB = headB;
while (curA != curB) {
curA = curA == null ? headB : curA.next;
curB = curB == null ? headA : curB.next;
}
return curA;
}
}
Python：
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB:
return None
curA , curB = headA , headB
while curA != curB:
curA = curA.next if curA else headB
curB = curB.next if curB else headA
return curA
欢迎关注公众号一起学习：爱写Bug
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/45198.html
摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。 爱写Bug（ID：iCodeBugs） 编写一个程序，找到两个单链表相交的起始节点。 Write a program to find the node at which the i...
摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...
摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。 一 目录 不折腾的前端，和咸鱼有什么区别...
摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...
摘要：还是链表算法题目描述给出两个无环单链表判断和是否相交。所以可以得出另外一种解法，先遍历链表，记住尾节点，然后遍历链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。想法还是奇妙的。算法写起来不难，难的是想到这个。 还是链表算法 题目描述：给出两个无环单链表A: a1 → a2 ↘ c1 → c2 → c3 → ...
阅读 1075·2021-11-25 09:43
阅读 1542·2021-10-25 09:47
阅读 2449·2019-08-30 13:46
阅读 739·2019-08-29 13:45
阅读 1266·2019-08-26 13:29
阅读 2963·2019-08-23 15:30
阅读 1085·2019-08-23 14:17
阅读 1311·2019-08-23 13:43
