public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<>();
        
        // 遍历链表A，记录所有节点
        ListNode curr = headA;
        while (curr != null) {
            visited.add(curr);
            curr = curr.next;
        }
        
        // 遍历链表B，找第一个出现在HashSet中的节点
        curr = headB;
        while (curr != null) {
            if (visited.contains(curr)) {
                return curr;  // 相交点
            }
            curr = curr.next;
        }
        
        return null;  // 不相交
    }
}

复杂度分析

时间复杂度：O(m + n)。两次遍历。
空间复杂度：O(m)。HashSet 存储链表 A 的所有节点引用。

三、解法二：优化解法——计算长度差对齐

思路

相交链表有一个重要性质：两个链表相交后，尾部是共享的。因此，如果先把两个指针对齐到"距离尾部等长"的位置，它们会同时到达相交点。

步骤：

分别计算 A 和 B 的长度 lenA 和 lenB
较长的链表的指针先走 |lenA - lenB| 步
两个指针同步前进，第一个相同节点就是相交点

完整代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        // 长的链表先走差值步
        while (lenA > lenB) {
            pA = pA.next;
            lenA--;
        }
        while (lenB > lenA) {
            pB = pB.next;
            lenB--;
        }
        
        // 同步前进，找相交点
        while (pA != pB) {
            pA = pA.next;
            pB = pB.next;
        }
        
        return pA;  // null 表示不相交，相交点直接返回
    }
    
    private int getLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}

复杂度分析

时间复杂度：O(m + n)。计算长度两次遍历 O(m+n)，对齐后同步走最多 O(min(m,n)) 步。
空间复杂度：O(1)。只用了常数个变量。

四、解法三：最优解法——双指针互换路径

思路

最精妙的解法，代码极简，背后是一个漂亮的数学证明。

核心思想：

设链表 A 的非公共部分长度为 a，链表 B 的非公共部分长度为 b，公共部分长度为 c
指针 pA 从 headA 出发，pB 从 headB 出发，同速前进
pA 走到 A 的末尾后，跳到 headB 继续走
pB 走到 B 的末尾后，跳到 headA 继续走

数学证明：

pA 走过的总路程：a + c + b（A的非公共部分 + 公共部分 + B的非公共部分） pB 走过的总路程：b + c + a（B的非公共部分 + 公共部分 + A的非公共部分）

两者走过的总路程完全相同，都是 a + b + c，所以它们同时到达相交点。

如果没有相交点： pA 走过 a + c + b 步后到达 null，pB 走过 b + c + a 步后也到达 null，两者同时到达 null，循环结束，返回 null。

完整代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode pA = headA;
        ListNode pB = headB;
        
        // 两个指针同速前进
        // 到达末尾后跳到对方的头节点
        // 相交时必然相遇，不相交时同时到达 null
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        
        return pA;  // 相交节点，或 null（不相交）
    }
}

复杂度分析

时间复杂度：O(m + n)。两个指针各自走过 a + b + c 步，即 O(m+n)。
空间复杂度：O(1)。只用了两个指针变量。

提交结果：时间击败约 100% 用户，空间击败约 95% 用户。

理解这个代码的关键：

pA = (pA == null) ? headB : pA.next;

这行代码意思是：如果 pA 走到了末尾（null），就跳到 headB；否则继续往前走。这不是"遇到 null 时跳转"，而是"到达 null 时进行一次切换"。这样每个指针恰好完成一次切换，走过的总路程相等。

六、踩坑实录

坑一：比较节点值而不是节点引用

// 错误：比较值，多个节点值相同时会误判
while (pA.val != pB.val) { ... }

// 正确：比较引用
while (pA != pB) { ... }

题目说"相交的起始节点"，是指同一个节点对象，不是值相同的节点。

坑二：跳转时机写错

// 错误：走到最后一个节点时就跳转（还没走到 null）
pA = (pA.next == null) ? headB : pA.next;

正确的写法是"走到 null 时才跳转"，即 pA == null 时跳到 headB。如果提前跳转，路程计算就出错了。

坑三：没有处理其中一个链表为空的情况

如果 headA 或 headB 本身就是 null，进入循环后 pA 或 pB 立刻就是 null，第一次迭代的跳转是 null -> headB 或 null -> headA，这在逻辑上是正确的——相当于"空链表走完了立刻切换到对方"。实际上不加空链表判断也能工作，但加上 if (headA == null || headB == null) return null; 可以更快退出，也更清晰。

坑四：误以为两链表长度相等时双指针会立刻相遇

长度相等时，pA 和 pB 不切换，直接同步走到相交点（或同时到 null）。这个情况下代码依然正确，因为 pA == pB 比较的是引用。

坑五：循环条件写成 pA != null && pB != null

这会导致有一个指针先到达 null 时退出循环，但另一个还没切换，返回结果错误。正确的循环条件是 pA != pB，两者同时到达 null 时，null == null 满足退出条件，返回 null。

七、总结

160 题的双指针解法是算法里我最喜欢的几个"数学之美"之一。代码只有5行，却包含了一个完整的等式证明：a + c + b = b + c + a，两个指针路程相等，因此同时到达相交点或同时到达 null。

这类题目告诉我们，算法题的最优解不一定是最复杂的，有时候是最简单的——简单到让人怀疑是否正确。真正的优雅来自对问题本质的深刻理解，而不是代码技巧的堆砌。

链表的七道经典题（206、92、25、141、142、148、160）至此全部讲完。这七道题覆盖了链表的绝大多数考点，把它们彻底搞懂，链表类面试题基本不会有太大问题。

双指针的数学证明你觉得优雅吗？欢迎评论区交流，点个在看支持。

相交链表——双指针等长的数学证明

相交链表——双指针等长的数学证明

开篇故事

一、题目解析

二、解法一：暴力解法——HashSet 记录节点

思路

完整代码

复杂度分析

三、解法二：优化解法——计算长度差对齐

思路

完整代码

复杂度分析

四、解法三：最优解法——双指针互换路径

思路

Mermaid 图——双指针路径

完整代码

复杂度分析

五、举一反三

同类题目

解题模板

六、踩坑实录

七、总结