好的，我们这次来详细讲解 LeetCode 第 160 题「相交链表」（Intersection of Two Linked Lists）。

1. 题目描述

题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。

注意：

• 相交的定义是基于节点的引用（内存地址），而不是节点的值。
• 保证整个链式结构中不存在环。
• 函数返回结果后，链表必须保持其原始结构。

示例 1：

A:      4 → 1 ↘
               8 → 4 → 5
B: 5 → 6 → 1 ↗

相交节点为值为 8 的节点（地址相同）。
输出：相交节点（引用）。

示例 2：

A: 2 → 6 → 4
B: 1 → 5

输出：null

2. 题意理解

• 两个链表可能长度不同。
• 如果相交，则从相交节点开始，之后的所有节点都是共有的（因为一个节点的 next 指针唯一）。
• 如果相交，则最后一个节点一定是相同的。
• 要求时间复杂度 O(m+n)，空间复杂度 O(1)。

3. 思路演进

3.1 暴力法（不可取）

• 对链表 A 的每个节点，遍历链表 B 看是否有相同地址的节点。
• 时间复杂度 O(m×n)，空间 O(1)，但会超时。

3.2 哈希集合法

• 遍历链表 A，把所有节点地址存入哈希集合。
• 遍历链表 B，检查当前节点是否在集合中，第一个在集合中的节点就是交点。
• 时间复杂度 O(m+n)，空间 O(m) 或 O(n)，不满足 O(1) 空间要求，但能通过。

3.3 双指针法（最优）

核心思想：
让两个指针分别从 headA 和 headB 出发，走完自己的链表后去走对方的链表，这样两个指针最终会：

• 要么在相交节点相遇（因为路程相同），
• 要么同时到达 null（不相交）。

为什么路程相同：
设链表 A 独有部分长度为 a，链表 B 独有部分长度为 b，公共部分长度为 c。

• 指针 pA 路线：a → c → b（A 独有 → 公共 → B 独有）
• 指针 pB 路线：b → c → a（B 独有 → 公共 → A 独有）

总长度都是 a + b + c，所以会在相交点相遇（如果相交），或者同时为 null（如果不相交）。

4. 算法步骤

1. 初始化指针 pA = headA, pB = headB。
2. 当 pA != pB 时循环：
   • 如果 pA 不为空，pA = pA.next，否则 pA = headB。
   • 如果 pB 不为空，pB = pB.next，否则 pB = headA。
3. 循环结束时的 pA（或 pB）就是相交节点（如果相交），或者是 null（如果不相交）。

5. 举例说明

例 1（相交）：

A: 4 → 1 ↘
          8 → 4 → 5
B: 5 → 6 → 1 ↗

• pA 路径：4 → 1 → 8 → 4 → 5 → (切到B)5 → 6 → 1 → 8
• pB 路径：5 → 6 → 1 → 8 → 4 → 5 → (切到A)4 → 1 → 8

在第二个 8 处相遇（即相交点）。

例 2（不相交）：

A: 2 → 6 → 4 → null → (切到B)1 → 5 → null
B: 1 → 5 → null → (切到A)2 → 6 → 4 → null

最终 pA 和 pB 同时为 null，返回 null。

6. 代码实现（Java）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode pA = headA, pB = headB;
        
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        
        return pA; // 要么是交点，要么是 null
    }
}

7. 复杂度分析

• 时间复杂度：O(m+n)，每个指针最多走 m+n 步。
• 空间复杂度：O(1)，只用了两个指针。

8. 关键点总结

• 理解“路程相等”的数学原理：a + c + b = b + c + a。
• 即使不相交，两个指针也会同时为 null，循环终止。
• 一定要判断初始空链表的情况。
• 这个方法很巧妙，需要画图帮助理解指针的移动路径。

这样一步步拆解，你是否对「相交链表」的双指针解法清晰了呢？