刷链表题的时候有一道题几乎每次复习都会翻出来面试题 02.07. 链表相交。题目要求很直接给定两个单链表的头节点 headA 和 headB返回两个链表相交的起始节点如果两个链表没有交点返回 null。很多人第一次看到这题会条件反射地想到用 unordered_set 把 A 链表的所有节点地址存下来再遍历 B 去查这样确实能做代码也不长。但面试官基本都会追问一句“能不能不用额外空间”这时候就需要双指针浪漫相遇解法。这篇文章会把两种解法的思路、代码、复杂度以及一个特别容易踩的坑掰开揉碎讲清楚尤其适合刚刷完链表基础题、准备系统性刷题或者准备面试的朋友。看懂这篇之后环形链表、合并链表这类题目也能顺带打通一部分。1. 先搞清楚题目到底在问什么1.1 什么是链表相交什么叫“交点”先说定义。两个链表相交指的是存在某个节点从它开始后面的节点全是同一个节点。也就是说两条链表从某一点开始“合并”成了一条链表这个合并点就是题目要返回的“交点”。举个例子A 链表是1 - 2 - 3 - 4 - 5 - NULLB 链表是9 - 3 - 4 - 5 - NULL其中 B 链表中值为 9 的节点的 next 指针指向的是 A 链表中值为 3 的那个节点。这时候从值为 3 的节点开始后面整条链都在内存中共享交点是 3。如果 B 的第二个节点只是恰好值也是 3但 next 指向的是另一个新建节点那不管打印出来值看起来多像两条链表实际上没有任何关系。这里要特别注意一个概念链表节点是内存地址的排列不是值的排列。两个节点的 val 相同、next 也相同仍然可能是两个独立节点。判断是否相交唯一可靠的依据是“节点的地址是否相同”。很多初学者会把链表题做成数组题拿着 val 去比较后面我会专门讲这个易错点。1.2 为什么说这题是面试常客链表题在面试中出现频率极高因为它代码量不大却能考察候选人会不会画图、能不能说清边界条件、能不能从暴力解法优化到更优解法。面试题 02.07 本质上和 LeetCode 160、剑指 Offer 52 是同一道题只是换了 OJ 和题号。你只要会这一道等于在三个题库里都拿下了分数。同时它也把链表问题里的几个重要基本功串起来了链表遍历、指针比较、边界判断、以及“能不能省空间”的优化意识。网上搜“leecode必刷基础算法题”“链表遍历”“单链表的基本操作”这些词的时候链表相交基本都会出现在前几页因为它不算难但又能帮你把双指针的敏感度练出来。很多人在刷完这题之后再去做环形链表 141、142会觉得快慢指针的思路顺了很多就是因为双指针这个套路在这里已经打通了。2. 最容易想到的解法unordered_set 哈希法2.1 思路与代码C哈希法的思路特别直观先遍历链表 A把每一个节点对象的指针都存进 unordered_set然后再遍历链表 B只要遇到第一个已经在集合里的节点那它就是交点。这里必须强调一句存的是ListNode*指针不是node-val。因为在 C 里unordered_setListNode*可以用来判断“某个节点是否出现过”而unordered_setint只能判断“某个值是否出现过”两者有天壤之别。后面讲易错点时我会拿错误写法做对比。#include unordered_set class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode* seen; ListNode* p headA; while (p ! nullptr) { seen.insert(p); p p-next; } p headB; while (p ! nullptr) { if (seen.count(p)) { return p; } p p-next; } return nullptr; } };这段代码逻辑上没有任何问题两个链表都遍历了一遍。先塞 A 再查 B时间上就是 O(m n)m 和 n 分别是两条链表的长度。第一个命中 B 中节点的位置就是第一个公共节点因为 A 中所有节点都已经被放进集合了。2.2 时间空间复杂度与适用场景这里放个对比表更清楚解法时间复杂度空间复杂度是否修改链表暴力两两比较O(m * n)O(1)否unordered_set 哈希O(m n)O(m)否双指针O(m n)O(1)否哈希解法适合哪些场景比如节点总数不多内存充足面试官没有额外要求或者你更想快速给出一个“肯定对”的答案先把题解出来再谈优化。面试中先讲哈希再讲双指针也是一种很自然的交流节奏因为面试官可以看出你有“优化意识”。但要注意哈希法虽然好写却不满足“进阶”要求。当面试官追问“能不能不开额外空间”时双指针解法就该登场了。同时如果链表特别长比如百万级节点用哈希集合会占用大量内存在嵌入式或内存受限的场景下O(m) 的空间成本不可接受。所以双指针往往才是这题被归为“基础必刷题”的真正原因。2.3 哈希解法的几个操作细节第一unordered_set需要包含头文件unordered_setLeetCode 后台有时候会自动引入但本地编辑器不一定最好自己写明。第二用count判断是否存在是可以的它返回 0 或 1也可以用find(p) ! seen.end()后者在语义上更明确。第三C 对指针类型默认支持哈希所以unordered_setListNode*可以直接用不需要自己写哈希函数。Python 里也可以照搬这个思路用内置的set存节点对象class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) - ListNode: seen set() p headA while p: seen.add(p) p p.next p headB while p: if p in seen: return p p p.next return NonePython 的节点对象默认以对象 id 为哈希依据所以p in seen判断的就是“同一个对象是否出现过”这正是我们要的语义。这里不要自作聪明去存p.val否则又掉进“用值判相交”的坑里了。3. 进阶解法双指针浪漫相遇3.1 双指针为什么能相遇推导双指针解法在社区里有个很浪漫的说法“你走过我走过的路我们终将相遇。”这句话听起来感性背后其实是严格的步数推导。假设链表 A 的独立部分长度为 a链表 B 的独立部分长度为 b公共部分长度为 c。也就是说A 总长度是 a cB 总长度是 b c。让 pA 从 headA 出发pB 从 headB 出发每次同时走一步。pA 走完 A 链表需要 a c 步pB 走完 B 链表需要 b c 步。这时候如果两个节点后面还有路我们让 pA 跳到 headB 继续走pB 跳到 headA 继续走。第二轮中pA 要到达交点需要先走完 B 的独立部分 b再走公共部分 c而 pB 要到达交点需要先走完 A 的独立部分 a再走公共部分 c。我们来算一下两个指针从起点到交点的总步数pA第一轮走完 A a c第二轮走到交点前又走了 b总步数是 a c b。pB第一轮走完 B b c第二轮走到交点前又走了 a总步数是 b c a。两个式子完全相等。两个指针速度相同走的步数相同那它们在到达交点的那一刻一定是同时到达。所以可以直接用pA pB作为循环终止条件。如果两条链表不相交公共长度 c 0。pA 的总步数会变成 a bpB 的总步数会变成 b a两个指针最终会同时走到 NULL。这时pA pB也成立循环退出返回 NULL。用一个生活化的类比来理解两个人从不同的门出发一个人先绕了 A 区域一整圈再进 B 区域另一个人先绕 B 区域一整圈再进 A 区域。只要最终的目标区域是同一个他们走的总路程必然相同就会同时出现在同一个地方。链表相交也是一样的逻辑。3.2 代码实现双指针的代码非常短但短代码往往更考验边界细节class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) { return nullptr; } ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; } };这段代码有几个点值得说。第一不要担心 pA 先到尾、pB 还没到尾时会死循环因为每次循环两个指针都只走一步移动是同步的。第二三目运算符的优先级是右结合的所以pA (pA nullptr) ? headB : pA-next;要加括号否则一些编译器会警告。第三加上最前面的空指针判断代码语义更清楚两个空链表也直接返回 NULL。有人会问为什么不相交时不会出现 pA 一直跳、pB 一直走导致永远不等的情况因为不管相不相交两个指针最终都会走完“自己的链表 对方的链表”。相交时它们走的总步数都是 a b c在交点相遇不相交时它们走的总步数都是 a b在 NULL 相遇。所以循环必然终止。3.3 两种写法对比哈希解法写起来快理解成本低适合作为敲开这道题的第一板斧。双指针解法空间更优面试表现力更强但需要证明“为什么能相遇”。两段代码都可以跑通 LeetCode没有对错只有场景选择。对比维度unordered_set 哈希双指针时间复杂度O(m n)O(m n)空间复杂度O(m)O(1)是否修改链表否否代码难度低中面试追问应对需要再优化已是 O(1) 空间如果在面试中我建议的节奏是先说暴力两两比较再说哈希最后说双指针并当场把 a、b、c 的推导画在纸上。这样整套回答既有亮点又显得逻辑完整。面试官喜欢听到的不是“我会用双指针”而是“我知道双指针为什么成立也知道它相比哈希省在哪里”。4. 一个关键易错点值相等不代表节点相等4.1 节点指针 vs 节点值这是这道题我最想单独拿一节来讲的点因为太多人在哈希法和双指针法里都挂在这个地方。链表节点的结构体里至少有两个字段val和next。val是业务数据next是地址。一个节点在内存里是一个对象有唯一地址。题目里说的“相交”要求的是“两个链表共享同一个节点对象”也就是 C 里的指针相等不是两个对象的内容相等。用生活场景类比一下两个人都叫“王刚”身份证号完全不同你不能说他们是同一个人。链表节点也是这样两个节点的val都是 3但一个在地址 0x100另一个在地址 0x200它们毫无关系。只有把地址看作“身份证号”才能判断是不是同一个节点。C 里比较两个节点是否相同用的是pa pb而不是pa-val pb-valJava 里用比较引用Python 里用is判断同一对象。千万不要用 Java 的equals它默认比较引用或可能被子类重写为比较值容易踩坑。4.2 为什么用指针比较而不用 val我们把错误写法摆出来看看// 错误示例用 val 判断 unordered_setint seen; while (pA) { seen.insert(pA-val); pA pA-next; } while (pB) { if (seen.count(pB-val)) return pB; pB pB-next; } return nullptr;这个代码在什么情况下会挂假设 A 是1 - 2 - 3 - 4B 是5 - 3 - 6。A 里的 3 和 B 里的 3 只是值相同后续链表完全不同。结果用 val 判断会错误地返回 B 中那个值为 3 的节点而正确答案是 NULL。LeetCode 的判题系统里会专门构造这类用例看起来两个链表有很多“相同值”但节点地址完全没交集。哈希解法里存ListNode*是安全的但一旦换成int就相当于把“节点身份”降级成了“节点值”丢失了最关键的信息。双指针解法中pA pB比较的是指针天然正确。这也是双指针解法不容易犯这个错误的原因之一但理解上还是要清楚。4.3 易错导致的问题和调试方法除了值和指针的问题这道题还有几个边界细节也值得记录。第一如果事先不判空双指针也能工作但加上判空会让逻辑更清晰。第二在循环里先移动指针再比较会跳过交点。正确写法应该是先判断pA pB再移动如果先移动再判断前一个交点就被漏掉了。第三本地测试时构造相交链表释放内存要格外小心。怎么调试最方便在遍历过程中直接打印节点地址std::cout pA: static_castvoid*(pA) pB: static_castvoid*(pB) std::endl;如果两个链表最终相交你会看到地址在某一步突然变成同一个如果一直不同最后同时变成0x0。比打印 val 直观得多。5. 实操过程与扩展从链表基础到相似题型5.1 手写链表基础方便本地调试很多人在 LeetCode 上能写出代码但本地一跑就懵因为 LeetCode 已经帮你把链表和测试框架搭好了。要真正理解链表相交我建议自己在本地构造一遍节点手动把公共部分链接起来。#include iostream #include unordered_set using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) return nullptr; ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; } }; int main() { // 公共部分 ListNode* common1 new ListNode(7); ListNode* common2 new ListNode(8); common1-next common2; // A: 1 - 2 - 7 - 8 ListNode* a1 new ListNode(1); ListNode* a2 new ListNode(2); a1-next a2; a2-next common1; // B: 5 - 7 - 8 ListNode* b1 new ListNode(5); b1-next common1; Solution s; ListNode* inter s.getIntersectionNode(a1, b1); if (inter) { cout Intersection: inter-val endl; } else { cout No intersection endl; } // 释放内存 delete b1; delete a1; delete a2; delete common1; delete common2; return 0; }这里特别提醒一下内存释放不要用循环从 A 的头部开始一直 deletenext否则会一路删到公共节点然后从 B 的头部再删一遍公共节点造成 double free。手动释放时分别释放各自独立段最后释放公共段是最直观也最安全的方式。5.2 常见扩展题链表相交练完之后可以顺势刷一批关联题目它们互相之间都有相通之处环形链表 141快慢指针判断是否有环。环形链表 II 142找到环的入口涉及 fast、slow 相遇后的二次推导。合并两个有序链表 21用哑节点和迭代指针完成归并。反转链表 206用 prev、cur、next 三个指针迭代反转。合并两个有序的单链表和 21 基本一致练的是链表操作基本功。单链表逆序热词里经常出现建议用迭代和递归两种方式各写一遍。单循环链表要注意尾节点指向头节点遍历终止条件不再是“遇到 NULL”而是“回到头节点”边界条件和普通链表不太一样。这些都做一遍之后你对指针 next 的敏感度会明显提升。链表相交里的双指针本质上和快慢指针、归并指针一样都是在“多个指针同步移动”的框架里找规律。5.3 测试用例设计写算法题不能只会跑 LeetCode 的样例本地一定要自己补用例。我常用的一组测试用例包括测试场景输入特点期望结果完全不相交A: 1-2B: 3-4NULL相交在中间A: 1-2-公共3-4B: 5-公共3-4节点 3相交在头节点A 和 B 的头是同一个节点头节点只有一个公共节点A: 1-公共5B: 2-公共5节点 5其中一条链表为空headA NULLNULL两条链表都为空headA NULL, headB NULLNULL值相同但不相交A: 1-2-3B: 4-3两个 3 地址不同NULL最后这个用例最容易暴露“用 val 判断”的错误强烈建议加进本地测试里。6. 面试现场怎么聊这题6.1 沟通节奏面试时不急着写代码先把这道题的定义和边界问清楚。比如可以问“相交是按节点地址判断还是按值判断”虽然题目通常已经定义了“公共节点”是同一个节点但主动确认能让面试官觉得你思考严谨。然后按难度递进讲思路先提最暴力的两两比较说明复杂度 O(m * n)再提 unordered_set 哈希把 A 的节点都存进集合遍历 B 查第一个命中节点如果面试官追问空间能否优化再自然地引出双指针。讲双指针时在纸上画出 a、b、c 三段标明 pA、pB 的走位并把两个指针的总步数推导写出来。这套流程走完面试官基本不会怀疑你“背题”因为每一步都有理有据。6.2 常见追问问得最多的几个问题我整理一下“如果链表可能有环怎么办”双指针解法会失效因为指针永远走不到 NULL也就不会触发跳转。这时要先判断是否有环或者用哈希集合先记录节点再决定如何处理。“如果只要求返回布尔值呢”代码基本不变把返回节点改成 true/false循环逻辑完全一样。“为什么双指针不会死循环”因为两个指针要么同时到交点要么同时到 NULLpA ! pB的条件总会退出。“如果内存非常紧张怎么办”双指针依然没问题因为它空间就是 O(1)在嵌入式场景下尤其合适。“Java/Python 里怎么比较”Java 用比较引用Python 用is判断同一对象。除非你明确要比较值否则不要用 equals 或 去比较对象内容。这道题我后来在真实面试里也遇到过当时面试官没有直接让写双指针而是先问“如果两个链表很长哈希集合内存可能不够你会怎么办”。那时候我已经把双指针推导跑熟了花了两分钟在白板上画完 a、b、c 的图再把代码写出来整个过程很顺畅。所以我的建议是不要只看题解一定要亲手推导一遍“为什么两个指针会相遇”这比背十遍代码都管用。