前言LeetCode 160 的题目是给定两个单链表的头节点找出它们相交的起始节点如果不存在交点返回空指针。题目里的「相交」不是值相等而是两个链表从某个节点开始指向同一个内存节点此后所有节点都完全重合。链表本身保证无环。最常见的错误是比较节点的值。值相等的两个节点可能位于完全不同的位置把它们当成交点后续逻辑全部错误。第二个错误是试图修改链表结构比如把某个链表首尾相接来制造环形再用快慢指针找入口这虽然能解但破坏了输入题目通常要求不能修改链表。第三个错误是双指针切换时不做空指针判断遇到长度不同且无交点的情况会解引用空指针。本文讲三种做法哈希集合、双指针切换、长度差对齐。其中双指针切换是空间最优的经典解法本文会给出它为什么正确的推演。示例以 C17 为准。一、题目模型与不变量设链表 A 的独有部分长度为 a链表 B 的独有部分长度为 b公共部分长度为 c。若 c 大于 0则两个链表在公共段的第一个节点相交若 c 等于 0则没有交点。注意 c 是「节点数」不是「值相等的节点数」公共段的每个节点地址都相同。从这个模型可以直接得到两个性质。第一两个链表的总长度分别是 ac 和 bc差值等于 a-b也就是说长度差只由独有部分决定。第二如果从两个头节点同时出发、同速前进那么走过 ac 和 bc 步后一个已经到尾另一个还差 |a-b| 步。对齐长度差就能让它们同时到达交点。哈希集合法和长度差法都直接利用这两条性质双指针切换则用一种更巧的方式让两个指针在走完自己的链表后跳到对方的头部从而自动补齐长度差。二、哈希集合先记录再查找最直观的做法是遍历链表 A把每个节点的地址放进哈希集合再遍历链表 B第一个能在集合里找到的节点就是交点。因为集合按指针哈希值相同但地址不同的节点不会被误判。时间复杂度 O(ac bc)也就是 O(mn)空间复杂度 O(m)m 是链表 A 的长度。这个方法容易写对适合面试时先给出一个能工作的版本再优化空间。用std::unordered_setconst ListNode*保存指针即可。不要保存int值否则相同值会碰撞出错误结果。遍历时用p p-next循环条件是p ! nullptr。三、双指针切换O(1) 空间的解法定义两个指针pa、pb分别从 A、B 的头节点出发每次各走一步。当pa走到空时把它重置到 B 的头节点当pb走到空时把它重置到 A 的头节点。两个指针相遇的节点就是交点如果没有交点它们会在走完两段链表后同时变成空指针。正确性可以用步数推演。pa的路径是 A 的 ac 个节点然后跳到 B 走 bc 个节点pb的路径是 B 的 bc 个节点然后跳到 A 走 ac 个节点。两者走的总步数都是 ab2c。在前 ac 步内pa到达 A 的末尾此时pb还在 B 的独有段或公共段切换之后pa从 B 头开始pb继续向 A 的头部方向走。由于两者总步数相同当它们走过 abc 步时必然同时到达交点若 c 为 0则同时到达空指针。这个证明的关键是「总路程相等」。可以把它想成两个人从不同的起点出发走完各自的路后交换路线最终会在相同的时间到达相同的位置。实现时要注意切换的写法。推荐写成pa pa ? pa-next : headB;pb pb ? pb-next : headA;这种写法先判断当前是否为空再决定是前进还是跳到另一个头。如果写成pa pa-next; if (!pa) pa headB;逻辑上也对但多一步且容易在空链表上出错。无论哪种循环条件都是pa ! pb不需要额外计数。四、长度差对齐第三种做法先分别求两个链表的长度让较长的指针先走 |la - lb| 步然后两个指针同时前进直到相遇或同时为空。它的时间和双指针切换一样是 O(mn)空间 O(1)但需要遍历两遍求长度代码更直白。对齐之后两个指针距离交点的步数相同所以要么在交点相遇要么同时走到空。这个方法的优点是容易解释缺点是长度需要单独计算且如果链表很长、只关心交点多遍历一遍略有浪费。五、完整示例// 适用于 C17#include cstddef#include iostream#include unordered_setstruct ListNode {int val;ListNode* next;explicit ListNode(int v) : val(v), next(nullptr) {}};// 方法一哈希集合ListNode* getIntersectionHash(ListNode* headA, ListNode* headB) {std::unordered_setconst ListNode* seen;for (ListNode* p headA; p ! nullptr; p p-next) {seen.insert(p);}for (ListNode* p headB; p ! nullptr; p p-next) {if (seen.count(p) ! 0) {return p;}}return nullptr;}// 方法二双指针切换ListNode* getIntersectionTwoPointers(ListNode* headA, ListNode* headB) {if (headA nullptr || headB nullptr) return nullptr;ListNode* pa headA;ListNode* pb headB;while (pa ! pb) {pa (pa ! nullptr) ? pa-next : headB;pb (pb ! nullptr) ? pb-next : headA;}return pa;}// 方法三长度差对齐int listLength(const ListNode* head) {int n 0;while (head ! nullptr) {n;head head-next;}return n;}ListNode* getIntersectionByLength(ListNode* headA, ListNode* headB) {int la listLength(headA);int lb listLength(headB);while (la lb) {headA headA-next;--la;}while (lb la) {headB headB-next;--lb;}while (headA ! headB) {headA headA-next;headB headB-next;}return headA;}int main() {ListNode a1(1), a2(2), a3(3);ListNode b1(4), b2(5);ListNode c1(7), c2(8);a1.next a2;a2.next a3;a3.next c1;b1.next b2;b2.next c1;c1.next c2;ListNode* r1 getIntersectionHash(a1, b1);ListNode* r2 getIntersectionTwoPointers(a1, b1);ListNode* r3 getIntersectionByLength(a1, b1);std::cout (r1 ? r1-val : -1) (r2 ? r2-val : -1) (r3 ? r3-val : -1) \n;return 0;}推演一下双指针的过程。A 独有 1、2、3 三个节点公共段是 7、8B 独有 4、5。pa走 1、2、3、7、8然后跳到 B 的 4、5、7pb走 4、5、7、8然后跳到 A 的 1、2、3、7。两者在 7 处首次相遇返回指向 7 的指针。如果两个链表没有公共段例如 A 是 1、2、3B 是 4、5pa走完 A 跳到 Bpb走完 B 跳到 A最终两者都变成nullptr循环条件pa ! pb不再成立返回空指针。这个过程不会死循环因为每次切换都让指针前进到一个确定的头部总步数有限。长度差版本里la为 5、lb为 4headA先走一步到 2两个指针距离交点都是 2 步之后同步前进在 7 处相遇。最后的while (headA ! headB)在无交点时会让两者同时变成空循环自然结束。六、边界与测试思路需要覆盖的边界包括任一链表为空、两个链表是同一个链表、交点就是某一个头节点、两个链表长度相同且无交点、两个链表长度不同且无交点、公共段只有一个节点。对每一种情况双指针法的循环都必须能在有限步内结束。如果要在本地验证可以构造节点后手工连接再用三种方法分别求交点比较返回的指针是否相同。注意不要用值比较代替指针比较那正是本文开头提到的错误。常见坑点坑点一比较节点的值而不是地址。❌if (pA-val pB-val) return pA;两个不同位置的同值节点被误判为交点。✅ 比较ListNode*指针本身例如pA pB或用哈希集合存地址。坑点二为了求解而修改链表。❌ 把 B 的尾节点接到 A 的头制造环后用快慢指针找入口。✅ 只读遍历需要 O(1) 空间时用双指针切换或长度差对齐。坑点三双指针切换时解引用空指针。❌pa pa-next;在pa已经是nullptr时执行。✅pa (pa ! nullptr) ? pa-next : headB;。坑点四切换逻辑写成循环重置导致死循环。❌ 每当pa为空就无条件重置到headB却没有让另一个指针前进可能永远错开。✅ 两个指针每轮各走一步空时切换一次循环条件用pa ! pb。坑点五不处理空链表。❌ 直接进入循环headA-next解引用空指针。✅ 开头判断任一为空就返回nullptr。坑点六长度差没有对齐就同步前进。❌ 求出长度后直接让两个指针一起走较长链表的指针先到交点后继续前进错过相遇点。✅ 先让较长的一方走|la - lb|步再同步前进。坑点七哈希集合存int值。❌std::unordered_setint seen;值重复导致误判。✅std::unordered_setconst ListNode* seen;按地址判重。坑点八认为交点一定在较长链表的尾部。❌ 只比较两个链表的最后几个节点忽略公共段可能很长。✅ 从对齐后的位置同步遍历第一个地址相同的节点就是交点。总结方法时间空间特点哈希集合O(mn)O(m)最直观适合先写出可行解双指针切换O(mn)O(1)代码短需理解总路程相等长度差对齐O(mn)O(1)逻辑直白需要先求长度这道题的关键是把「相交」理解为节点地址相同而不是值相同。三种方法本质上都在解决同一件事消除两个链表在交点之前的长度差。哈希集合用空间换时间双指针切换用「走对方的路」自动补齐长度差法则显式对齐。理解了这个共同点就不需要死记代码。