好的，我们这次来详细讲解 LeetCode 第 160 题「相交链表」。

这道题非常经典，考察的是对链表结构的理解和双指针技巧的灵活运用。

1. 题目描述

题目链接：LeetCode 160

难度：简单

标签：哈希表、链表、双指针

题目描述：

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

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

注意：

• 函数返回结果后，链表必须 保持其原始结构。
• 如果两个链表相交，则相交节点后的所有节点都是两个链表共有的。
• 你可以假设整个链表结构中没有循环。

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

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

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

2. 直观理解与示例

我们先通过一个例子来理解题意。

示例 1：

链表 A:      4 -> 1 -> 8 -> 4 -> 5
链表 B: 5 -> 0 -> 1 -> 8 -> 4 -> 5

这两个链表在值为 8 的节点处相交。注意，相交节点不是值相等，而是 同一个节点（内存地址相同）。相交节点之后的部分（8 -> 4 -> 5）是两个链表共有的。

我们需要找到的就是第一个公共节点，即值为 8 的那个节点。

3. 解题思路演进

思路一：暴力法（不推荐）

最直接的方法是，对于链表 A 的每一个节点，都去遍历整个链表 B，检查是否有节点相同。

• 时间复杂度：O(m * n)，其中 m 和 n 分别是链表 A 和 B 的长度。效率太低。
• 空间复杂度：O(1)。

这种方法在链表较长时不可行。

思路二：哈希表法

我们可以先遍历链表 A，将所有节点的引用（地址）存入一个哈希集合（HashSet）中。然后遍历链表 B，对于 B 中的每个节点，检查它是否存在于哈希集合中。第一个存在的节点就是相交节点。

• 时间复杂度：O(m + n)，我们分别遍历了两个链表各一次。
• 空间复杂度：O(m)，用于存储链表 A 的节点引用。

这是一种有效的方法，代码也容易写。但面试官可能会追问：“能否满足 O(1) 的空间复杂度？”

思路三：双指针法（最优解）

这才是本题的精髓。我们需要一种方法，让两个指针能够“对齐”地遍历到可能的交点。

核心观察：

• 设链表 A 的独有部分长度为 a，链表 B 的独有部分长度为 b，两个链表的公共部分长度为 c。
• 那么链表 A 的总长度为 a + c，链表 B 的总长度为 b + c。

巧妙的想法：

• 让指针 pA 从链表 A 的头开始遍历，指针 pB 从链表 B 的头开始遍历。
• 当 pA 遍历完链表 A 后，让它从链表 B 的头开始继续遍历。
• 当 pB 遍历完链表 B 后，让它从链表 A 的头开始继续遍历。
• 如果两个链表有相交点，那么 pA 和 pB 最终会在相交点相遇。为什么呢？

原因：

• pA 走过的总路径是 a + c + b。
• pB 走过的总路径是 b + c + a。
• 很明显，a + c + b = b + c + a。
• 所以，两个指针在第二次遍历时（切换链表后），会 同时 到达第一个公共节点！

如果两个链表不相交：

• 那么两个指针最终都会走过 m + n 的长度，同时变为 null，循环结束，返回 null。

这个方法完美地解决了问题，且只需要 O(1) 的额外空间。

4. 算法步骤（双指针法）

1. 初始化两个指针 pA 和 pB，分别指向链表 A 和链表 B 的头节点。
2. 进入一个循环，只要 pA 不等于 pB，就继续循环：
   a. 将 pA 向后移动一个节点。如果 pA 变为 null，则将其重定位到链表 B 的头节点。
   b. 将 pB 向后移动一个节点。如果 pB 变为 null，则将其重定位到链表 A 的头节点。
3. 循环结束时，pA（或 pB）指向的就是相交节点（如果存在），或者是 null（如果不存在相交）。

5. 代码实现（Java）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 边界情况：如果任一链表为空，则不可能相交
        if (headA == null || headB == null) {
            return null;
        }

        // 初始化两个指针
        ListNode pA = headA;
        ListNode pB = headB;

        // 主要循环
        while (pA != pB) {
            // 如果 pA 走到链表A的末尾，就切换到链表B的头
            pA = (pA == null) ? headB : pA.next;
            // 如果 pB 走到链表B的末尾，就切换到链表A的头
            pB = (pB == null) ? headA : pB.next;
        }

        // 循环退出时，pA 和 pB 要么指向相交节点，要么都指向 null（不相交）
        return pA;
    }
}

6. 详细示例演示

我们以示例 1 来走一遍算法流程：

链表 A: 4 -> 1 -> 8 -> 4 -> 5 (交点 8)
链表 B: 5 -> 0 -> 1 -> 8 -> 4 -> 5 (交点 8)

步骤：

1. pA 在 4, pB 在 5。4 != 5，移动。
2. pA 移动到 1, pB 移动到 0。1 != 0，移动。
3. pA 移动到 8, pB 移动到 1。8 != 1，移动。
4. pA 移动到 4, pB 移动到 8。4 != 8，移动。
5. pA 移动到 5, pB 移动到 4。5 != 4，移动。
6. 关键步骤：pA 移动到 null（A 结束），根据算法，pA 切换到链表 B 的头节点 5。pB 移动到 5（B 结束），根据算法，pB 切换到链表 A 的头节点 4。
   • 现在 pA 在 B:5, pB 在 A:4。5 != 4，移动。
7. pA 移动到 B:0, pB 移动到 A:1。0 != 1，移动。
8. pA 移动到 B:1, pB 移动到 A:8。1 != 8，移动。
9. pA 移动到 B:8, pB 移动到 A:8。
   • 此时 pA == pB，循环结束。返回 pA 指向的节点 8。

可以看到，两个指针最终在交点处相遇。

7. 复杂度分析

• 时间复杂度：O(m + n)。最坏情况下，每个指针需要遍历两个链表的总长度。
• 空间复杂度：O(1)。只使用了两个指针变量。

8. 总结

这道「相交链表」题目的巧妙之处在于利用了数学上的等量关系（a + c + b = b + c + a），通过双指针的“浪漫相遇”方式，在 O(1) 的空间内高效解决了问题。

核心要点：

1. 理解题意：相交是指节点对象相同（内存地址相同），而非值相同。
2. 掌握双指针技巧：当两个链表长度不一致时，通过交换遍历路径来“弥补”长度差，是解决此类问题的常用技巧。

希望这个从理解、思路演进到代码实现的详细讲解能让你彻底掌握这道题！