相交链表

给你两个单链表的头节点 headA 和 headB。

请你找出并返回两个单链表相交的起始节点。

如果两个链表不存在相交节点，返回 null。

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

注意：

• 函数返回结果后，链表必须保持其原始结构。
• 链表相交指的是两个链表从某个节点开始，后续节点在内存中是同一批节点。
• 不能只比较节点值是否相等，必须比较节点本身是否相同。

自定义评测中会使用：

• 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。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
注意相交节点的值不为 1，因为两个值为 1 的节点在内存中是不同节点。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2。
从各自的表头开始算起，链表 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
解释：这两个链表不相交，因此返回 null。

提示：

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

进阶：

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

解法一（哈希集合）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;

        ListNode* cur = headA;
        while (cur != nullptr)
        {
            visited.insert(cur);
            cur = cur->next;
        }

        cur = headB;
        while (cur != nullptr)
        {
            if (visited.count(cur))
            {
                return cur;
            }

            cur = cur->next;
        }

        return nullptr;
    }
};

解法二（双指针同步走）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pA = headA;
        ListNode* pB = headB;

        while (pA != pB)
        {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }

        return pA;
    }
};

核心思想

这题最容易误解的地方是：相交不是指节点值相等，而是指两个指针指向同一个节点。

例如示例 1 中，两个链表里都有值为 1 的节点，但这两个节点在内存中不是同一个节点，所以它们不是相交节点。

真正的相交节点是值为 8 的那个节点，因为从这个节点开始，两个链表共享同一段后续链表。

最直观的做法是：

• 先把链表 A 中所有节点存进哈希集合
• 再遍历链表 B
• 第一个已经出现在哈希集合中的节点，就是相交起点

这个方法很好理解，但需要 O(m) 额外空间。

进阶要求只使用 O(1) 内存，所以更推荐双指针做法。

这题最关键的观察是：

让两个指针分别走完 A + B 和 B + A，它们走过的总长度相同，因此如果存在相交节点，一定会在相交起点相遇。

解法一：哈希集合

先遍历链表 A，把每个节点指针都放进哈希集合：

visited.insert(cur);

注意这里存的是 ListNode*，也就是节点地址，而不是节点值。

然后遍历链表 B。

如果某个节点已经在哈希集合中出现过：

visited.count(cur)

说明这个节点既属于链表 A，也属于链表 B。

由于我们是从 headB 开始向后遍历，第一次遇到的公共节点就是两个链表相交的起始节点。

如果遍历完整个链表 B 都没有找到公共节点，说明两个链表不相交，返回 nullptr。

解法二：双指针同步走

使用两个指针：

• pA 从 headA 出发
• pB 从 headB 出发

每次两个指针都向后走一步。

当 pA 走到链表 A 的末尾后，让它跳到 headB。

当 pB 走到链表 B 的末尾后，让它跳到 headA。

代码就是：

pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;

这样做的效果是：

• pA 走过的路径是：链表 A + 链表 B
• pB 走过的路径是：链表 B + 链表 A

如果两个链表相交，它们会在相交起点相遇。

如果两个链表不相交，它们最终会同时变成 nullptr，循环结束后返回 nullptr。

为什么双指针会对齐

假设链表 A 独有部分长度为 a，链表 B 独有部分长度为 b，公共部分长度为 c。

那么：

• 链表 A 的总长度是 a + c
• 链表 B 的总长度是 b + c

如果两个链表长度不同，直接同时从头走，较长链表的指针会更晚进入公共部分。

双指针切换链表以后：

• pA 走过的长度是 a + c + b
• pB 走过的长度是 b + c + a

这两个长度相等，都是：

a + b + c

所以两个指针会在走完各自独有部分后，同时到达公共部分的起点。

也就是相交节点。

为什么链表结构不会被改变

两种解法都只读取节点的 next 指针，并移动临时变量。

代码中没有修改：

node->next

也没有新建节点接到原链表中。

所以函数返回后，链表仍然保持原始结构。

正确性证明

我们证明：双指针算法返回的节点满足题意。

结论 1：如果两个链表相交，两个指针一定会在相交起点相遇

设链表 A 独有部分长度为 a，链表 B 独有部分长度为 b，公共部分长度为 c。

指针 pA 先走链表 A，再走链表 B。

在到达相交起点前，它走过：

a + c + b

步。

指针 pB 先走链表 B，再走链表 A。

在到达相交起点前，它走过：

b + c + a

步。

两者长度相同。

因此，当两个指针都完成一次换头以后，它们会同时到达公共部分的起点。

由于公共部分从相交节点开始完全相同，所以此时：

pA == pB

算法返回这个节点。

结论 2：如果两个链表不相交，两个指针最终会同时变成 nullptr

如果两个链表不相交，那么不存在任何一个实际节点同时属于链表 A 和链表 B。

pA 走过的路径是链表 A 加链表 B。

pB 走过的路径是链表 B 加链表 A。

两条路径的总长度都为：

m + n

所以两个指针都会在走完 m + n 步后到达末尾。

由于没有公共节点，它们不会在中途相遇，最终会同时变成 nullptr。

此时循环结束，算法返回 nullptr。

结论 3：算法不会错误返回值相同但地址不同的节点

循环条件判断的是：

pA != pB

这里比较的是两个节点指针是否相同，也就是是否指向同一个节点。

并没有比较：

pA->val == pB->val

因此即使两个不同节点的值相同，算法也不会把它们误判为相交。

得出结论

由结论 1 可知，如果两个链表相交，算法一定返回相交起点。

由结论 2 可知，如果两个链表不相交，算法一定返回 nullptr。

由结论 3 可知，算法判断的是节点本身相同，而不是节点值相同。

因此双指针算法正确。

举例理解

以示例 1 为例：

listA = [4, 1, 8, 4, 5]
listB = [5, 6, 1, 8, 4, 5]

其中两个链表从值为 8 的节点开始相交。

链表 A 独有部分是：

4 -> 1

链表 B 独有部分是：

5 -> 6 -> 1

公共部分是：

8 -> 4 -> 5

指针 pA 的路径是：

A 独有部分 -> 公共部分 -> B 独有部分 -> 公共部分

指针 pB 的路径是：

B 独有部分 -> 公共部分 -> A 独有部分 -> 公共部分

两者在换到对方链表后，走过的总长度被拉平。

最终会同时到达公共部分的起点，也就是值为 8 的节点。

复杂度分析

解法一

设链表 A 的长度为 m，链表 B 的长度为 n。

哈希集合需要存储链表 A 中的所有节点。

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

解法二

两个指针最多各走完链表 A 和链表 B 一次。

总步数是线性的。

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

解法二满足进阶要求，是更推荐的做法。