LeetCode：相交链表

1、题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

实例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

实例2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [1,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
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

2、方法1：哈希集合

解题思路：

初始化哈希集合：创建一个 HashSet 来存储链表 A 的节点引用。
遍历链表 A：
- 将链表 A 的每个节点依次加入 HashSet。
遍历链表 B：
- 对于链表 B 的每个节点，检查是否存在于 HashSet 中。
- 如果存在，则该节点就是相交的起始节点，直接返回。
遍历结束：
- 如果链表 B 遍历完毕仍未找到相交节点，返回 null。

关键点：

时间复杂度：O(m + n)，其中 m 和 n 分别是链表 A 和 B 的长度。
空间复杂度：O(m)，最坏情况下需要存储链表 A 的所有节点。

    //使用哈希集合解题，先遍历其中一个链表，并将其每个节点存储到哈希集合中//遍历另外一个链表的时候，第一次判断该链表的结点存在于哈希结合中，那一定就是相交的结点public static ListNode getIntersectionNode(ListNode A, ListNode B){if (A == null || B == null) return null;HashSet<ListNode> hashSet = new HashSet<>();//先将A链表的结点入哈希集合中，在后续遍历链表B的时候，再来判断哈希集合是否有存在链表B的节点，当第一个的时候也就是相交的节点while (A != null){hashSet.add(A);A = A.next;}while (B != null){if (hashSet.contains(B)){return B;}B = B.next;}return null;}

3、方法2：双指针

解题思路：

初始化指针：
- 指针 A 指向链表 A 的头节点 headA。
- 指针 B 指向链表 B 的头节点 headB。
同步遍历链表：
- 指针 A 和 B 同时每次移动一步。
- 如果 A 到达链表 A 的末尾（null），则将其重定向到链表 B 的头节点 headB。
- 如果 B 到达链表 B 的末尾（null），则将其重定向到链表 A 的头节点 headA。
相遇条件：
- 当 A 和 B 指向同一个节点时，该节点就是相交的起始节点。
- 如果 A 和 B 同时到达 null，说明链表无交点。

关键点：

数学原理：
- 设链表 A 的非公共部分长度为 a，链表 B 的非公共部分长度为 b，公共部分长度为 c。
- 指针 A 走过的路径：a + c + b。
- 指针 B 走过的路径：b + c + a。
- 两者路径长度相同，因此会在相交点相遇。
时间复杂度：O(m + n)。
空间复杂度：O(1)，仅需两个指针。

    //使用双指针解题，// 指针A遍历到链表A的尾结点null时，将指针A指向链表B，继续遍历链表B// 同时，指针B遍历到链表B的尾结点null时，也是将指针B指向链表A，继续遍历链表A// 当指针A和指针B相遇的时候，一定是相交点public static ListNode getIntersectionNode(ListNode headA, ListNode headB){if (headA == null || headB == null) return null;ListNode A = headA;ListNode B = headB;while (A != B){A = A==null? headB:A.next;B = B==null? headA:B.next;}return A;}

4、方法3：快慢指针

解题思路：

计算链表长度：
- 遍历链表 A 和 B，分别计算长度 lenA 和 lenB。
对齐起点：
- 计算长度差 differ = |lenA - lenB|。
- 将较长链表的指针向后移动 differ 步，使得剩余部分长度相同。
同步遍历：
- 两个指针同时每次移动一步，直到指向同一节点。
- 如果遍历到 null 仍未相遇，说明无交点。

关键点：

时间复杂度：O(m + n)。
空间复杂度：O(1)。

    // 使用快慢指针解题// 遍历两个链表获得各个链表的长度，并得到长度之差  differ = |lenA - lenB|// 然后将较长的指针，直接跳过differ个结点，遍历链表，当两个指针指向同一个节点时，说明该节点就是相交节点public static ListNode getIntersectionNode2(ListNode headA, ListNode headB){int lenA=0,lenB=0,differ=0;ListNode A=headA, B=headB;while (headA != null){lenA++;headA = headA.next;}while (headB != null){lenB++;headB = headB.next;}differ = Math.abs(lenB - lenA);if (lenA < lenB){for (int i = 0; i < differ; i++) {B = B.next;  //这里以B和A来作为快慢指针,是因为前面的headA, headB已经移动过位置了，而下面是需要从头开始遍历的}}else {for (int i = 0; i < differ; i++) {A = A.next;}}while (A != null && B != null){if (A == B) return A; //刚好相等时，就是相交点A = A.next;B = B.next;}return null;//否则退出循环，则说明无交点}