解法)
## 1. 这道题为什么值得写面试高频与链表操作的试金石 相交链表Intersection of Two Linked Lists在 LeetCode 上是编号 160 的经典题在《剑指 Offer》里对应第 52 题。我见过不少面试官拿它当热身题也见过它作为二面手写题的升级版出现——比如要求不用哈希表、空间复杂度压到 O(1)。这道题表面上看只是找两个链表有没有交点实际上考察的是**链表指针操作的基本功、边界条件的敏感度、以及用数学思维化简问题的能力**。 先说清楚题目本身用一句人话概括就是给你两个单链表的头节点 headA 和 headB判断这两个链表是否在某个节点处汇合如果汇合返回那个相交节点的指针如果不相交返回 NULL。注意一个关键前提——**两个链表一旦相交从相交节点开始后面的所有节点都是共享的**因为它们都是单链表每个节点只有一个 next 指针不可能出现相交之后又分叉的情况。这一点是整个题目所有解法成立的基础。 链表的相交结构长什么样我画个文字版的示意图方便你对着理解A: a1 - a2c1 - c2 - c3 / B: b1 - b2 - b3在这个结构里A 链表从 a1 出发走到 a2 之后进入 c1B 链表从 b1 出发经过 b1、b2、b3 之后也进入 c1。c1 就是相交节点c1、c2、c3 是两个链表共享的部分。注意A 的长度是 4a1、a2、c1、c2、c3一共5个我数错了重来a1、a2、c1、c2、c3是5个节点B 的长度是 5b1、b2、b3、c1、c2、c3但公共部分只有 3 个节点。 为什么说这道题是链表操作的试金石因为链表是 C 语言里最讲究指针的语义的数据结构。写数组题你操作的是一段连续内存、下标直接可算写链表题你手里只有一个指向头节点的指针所有后续节点都要靠 next 一步步走。相交链表这个题目涉及的指针移动、长度差计算、循环退出条件稍有疏忽就会踩空指针的坑。而且 C 语言没有现成的链表库一切都要自己定义结构体、自己管理内存这对指针理解的考察比其他语言更深入。 这篇博文适合正在刷题的在校生、准备面试的求职者也适合工作中偶尔需要手写数据结构的 C 语言开发者。我会从最朴素的做法开始逐步讲到最优解再附上我实际调试过程中踩过的坑和排查经验。 ## 2. 先搞定最容易想到的方案哈希表与暴力双循环 ### 2.1 哈希表方案思路最直但空间换时间 最简单的思路是这样既然相交链表从交点开始共享节点那我只要把一个链表的所有节点地址记下来然后遍历另一个链表逐个检查当前节点的地址是否在刚才的记录里。如果在那这个节点就是交点如果走完都没找到说明两个链表不相交。 C 语言实现这个方案可以用哈希表也可以用借用数组当标记的办法——但注意这里存的是**指针地址**不是整数值所以直接用数组下标做哈希的话你得把指针转换为整数再哈希。我这里的示例代码用了一个简单的哈希结构你也可以直接用带哨兵的双重循环先跑通功能。 c #include stdio.h #include stdlib.h struct ListNode { int val; struct ListNode *next; }; #define HASH_SIZE 1024 struct HashNode { struct ListNode *addr; struct ListNode *next; // 链地址法解决冲突 }; struct HashNode *hash_table[HASH_SIZE]; unsigned int hash_ptr(struct ListNode *p) { return ((unsigned long)p 4) % HASH_SIZE; } void hash_insert(struct ListNode *p) { unsigned int idx hash_ptr(p); struct HashNode *node (struct HashNode *)malloc(sizeof(struct HashNode)); node-addr p; node-next hash_table[idx]; hash_table[idx] node; } int hash_find(struct ListNode *p) { unsigned int idx hash_ptr(p); struct HashNode *cur hash_table[idx]; while (cur) { if (cur-addr p) return 1; cur cur-next; } return 0; } struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { for (int i 0; i HASH_SIZE; i) hash_table[i] NULL; // 每次调用前清空 struct ListNode *p headA; while (p) { hash_insert(p); p p-next; } p headB; while (p) { if (hash_find(p)) return p; p p-next; } return NULL; }这个方案的时间复杂度是 O(m n)其中 m 和 n 分别是两个链表的长度因为遍历一次 A 链表做插入遍历一次 B 链表做查找。空间复杂度是 O(m)因为需要把 A 链表的所有节点地址存下来。这个方案在面试时可以作为我第一时间想到的解法说出来但通常面试官会接着问一句能不能把空间复杂度降到 O(1)这就是下面两个方案的出场时机了。2.2 暴力双循环最笨但最容易验证思路如果不想引入哈希表另一个直观方案是双循环对 A 链表的每个节点都完整遍历一遍 B 链表检查有没有指针相等的节点。伪代码如下struct ListNode *pA headA; while (pA) { struct ListNode *pB headB; while (pB) { if (pA pB) return pA; pB pB-next; } pA pA-next; } return NULL;这个写法最直白时间复杂度是 O(m * n)空间复杂度是 O(1)。它的优点是不容易写错尤其适合你在本地快速验证两个链表到底相不相交、交点在哪这个事实。但它的缺点很明显一旦链表长度上万性能就会急剧下降。我个人的建议是如果你在面试中先说哈希表方案再优化到双指针方案完全没有必要再提暴力双循环。但如果你是在自己学习调试阶段暴力双循环是很好的辅助验证工具——你可以用它跑一遍测试用例确认自己的预期结果再去改写成更优的方案。2.3 为什么哈希表方案在 C 语言里要特别小心这里必须提醒一个 C 语言特有的坑哈希表的键是指针值而不是节点里的 val。我见过不少人刚上手这道题时想用节点值 val 作为比较依据结果两个链表里有两个值相同的节点但它们的地址完全不同就被误判成相交了。链表相交判断的本质是判断节点是否同一个不是判断值是否相等。另外哈希表方案里如果你用(unsigned long)p 4做哈希是把指针右移 4 位因为典型的链表节点通过 malloc 分配时地址通常按 16 字节对齐低位基本为 0右移后哈希分布更均匀。这个技巧在嵌入式或者教学场景下能提升一点性能但不必过度优化。真正在工程里我更倾向于直接用双指针方案省去所有哈希表内存管理的麻烦。3. 高效解法一长度差法先对齐再同步走3.1 核心思想把长度差这个变量消掉哈希表和暴力法的本质问题在于两个链表长度不等时你没法简单地让两个指针同步往前走。但如果我们换个角度看如果两个链表相交那么从交点到尾部的公共部分长度是相同的。因此两个链表的长度差必然完全来自交点之前的独有部分。这么说可能有点绕我举一个例子。假设 A 链表长度为 7B 链表长度为 5交点位于 A 的第 3 个节点、B 的第 1 个节点。那么A 的独有部分长度 3 - 1 2a1、a2B 的独有部分长度 1 - 1 0公共部分长度 5 - 1 1不对我重新算一下。公共部分是从交点开始到尾部这个长度对两个链表是一样的。如果 A 总长 7交点前有 2 个独有节点那交点后的公共长度就是 7 - 2 - 1交点头本身其实不用这么纠结关键结论只有一个两个链表的长度差就等于两个指针各自走到交点所需步数的差。如果能让两个指针从距离交点相同步数的位置出发那么它们同步前进必然会在交点相遇。长度差法的具体操作分三步分别遍历两个链表得到长度 lenA 和 lenB。让较长的链表先走abs(lenA - lenB)步这样两个指针就处在距离链表末尾相同距离的位置。然后两个指针同步前进每走一步比较一次相等则返回该节点走到 NULL 都没相遇说明不相交。3.2 C 语言完整实现与测试直接上代码struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int lenA 0, lenB 0; struct ListNode *pA headA, *pB headB; // 第一遍统计两个链表的长度 while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } // 重新指向头节点 pA headA; pB headB; // 让较长的链表先走长度差 int diff lenA - lenB; if (diff 0) { while (diff--) pA pA-next; } else { diff -diff; while (diff--) pB pB-next; } // 同步前进比较指针地址 while (pA pB) { if (pA pB) return pA; pA pA-next; pB pB-next; } return NULL; }我在本地跑了几组测试第一组两个链表不相交headA: 1 - 2 - 3 headB: 4 - 5 - 6 期望结果NULL运行过程lenA3lenB3长度差为 0两个指针从头同步走走到 NULL 都没有相等返回 NULL。正确。第二组两个链表相交headA: 1 - 2 - 3 - 4 - 5 headB: 6 - 3 - 4 - 5 交点值 3假设地址相同 期望结果返回值为 3 的节点指针运行过程lenA5lenB4diff1pA 先走一步来到指向 2 的节点。此时 pA 距离交点节点 3还有 1 步pB 距离交点节点 6 的下一个也就是节点 3也是 1 步。然后同步走pA 到节点 3pB 也到节点 3地址相等返回。正确。3.3 这个方案的边界条件与常见错误写这个代码时最容易犯的错误有三个我一个个说。第一个错误统计长度后忘记把指针重置回头节点。这几乎是每个初学者都会踩的坑。两个 while 循环走完之后pA 和 pB 都已经指向 NULL 了如果不重新赋值pA headA; pB headB;后面的逻辑全部白写。第二个错误处理长度差时符号搞反。如果 lenA lenB你让 pA 先走 diff 步反之让 pB 走。这个 if-else 分支本身不难但如果你写到一半改动了变量的含义很容易把diff -diff的逻辑丢掉导致指针越界。我建议先写一个int diff lenA - lenB;然后统一处理比如if (diff 0) { while (diff) pB pB-next; } else { while (diff--) pA pA-next; }这里注意diff为负时diff是将负数逐步增加直到 0效果正好是让 pB 先走-diff步。这个写法在 C 语言里完全合法但读代码的人需要想一下注释写清楚比较好。第三个错误同步前进时只判断 val 相等而不是地址相等。我在前面已经强调过了pA-val pB-val只能说明两个节点的值相同不能说明它们相交。必须判断pA pB这是指针比较比较的才是地址。长度差法的时间复杂度是 O(m n)空间复杂度 O(1)已经能满足绝大多数面试要求了。但 LeetCode 的官方题解还给出了更巧妙的双指针法——两个指针走对方的路连长度差都不用先算。这就是下一节的内容。4. 高效解法二双指针交替法最优雅的 O(1) 方案4.1 为什么两个指针走完各自的路再走对方的路就能相遇这个解法的代码极短但理解起来需要绕一个弯。我先给出代码再解释原理。struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (!headA || !headB) return NULL; struct ListNode *pA headA; struct ListNode *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }就这么几行。我第一次看到这个解法时愣了一下因为它的逻辑太绕了——两个指针都不停地走走到 NULL 就跳到另一个链表的头部直到它们相遇。但仔细推演之后发现这实际上是长度差法的另一种表达而且连算长度这个步骤都省了。假设链表 A 长度为 m链表 B 长度为 n交点前的独有部分分别为 a 和 b公共部分长度为 c。那么m a cn b c当 pA 走完 A 链表走了 m 步时它会跳到 headB 继续走当 pB 走完 B 链表走了 n 步时它会跳到 headA 继续走。如果两个链表相交pA 一共走m b步后pB 一共走n a步后它们都会到达交点。我们来验证这个步数一致性pA 走到交点需要的总步数 A 链表独有部分 a 公共部分 c不对这里要重新算。pA 从 headA 出发走到 A 链表的交点需要 a 1 步不对我不用步数精确到个位只看相对关系。更简洁的理解方式是这样pA 总共走过的路径是A 链表全部 B 链表交点之前的独有部分也就是m bpB 总共走过的路径是B 链表全部 A 链表交点之前的独有部分也就是n a。由于m b (a c) b a b c n a (b c) a a b c所以当 pA 走完m b步、pB 走完n a步时它们走过的总步数相同而且此时它们都正好站在交点上。这就是殊途同归。如果两个链表不相交那么 pA 走完m n步、pB 也走完n m步后它们会同时走到 NULL即pA pB NULL循环退出返回 NULL。4.2 逐步推演用一个具体例子走一遍纸上得来终觉浅我手动推演一遍。假设 A 链表a1 - a2 - c1 - c2 - NULLB 链表b1 - b2 - b3 - c1 - c2 - NULL。交点 c1。初始化pA 指向 a1pB 指向 b1。第 1 步循环pA ! pBpA 指向 a2pB 指向 b2。 第 2 步循环pA ! pBpA 指向 c1pB 指向 b3。 第 3 步循环pA ! pBpA 指向 c2pB 指向 c1。 第 4 步循环pA ! pBpA 向后走此时 pA 在 c2 的 next也就是 NULLpB 从 c1 走到 c2。根据代码逻辑pA 为 NULL所以 pA 被赋值为 headB即 b1pB 不为 NULL所以 pB 指向 c2。第 5 步循环pA现在指向 b1! pB指向 c2pA 走到 b2pB 走到 NULL于是 pB 被赋值为 headA即 a1。 第 6 步循环pA 指向 b2pB 指向 a1不相等pA 走到 b3pB 走到 a2。 第 7 步循环pA 指向 b3pB 指向 a2不相等pA 走到 c1pB 走到 c1。 第 8 步循环pA pB跳出循环返回 c1。从第 1 步到第 8 步pA 实际遍历了 A 的全部 4 个节点又遍历了 B 靠近交点之前的独有部分 b1、b2、b3pB 遍历了 B 的全部 5 个节点又遍历了 A 靠近交点之前的独有部分 a1、a2。两者最终在 c1 相遇。看起来很神奇其实就是前面证明的恒等式在起作用。4.3 这个解法与长度差法的本质联系很多人会问双指针交替法和长度差法到底哪个更好我的答案是它们在数学上是等价的只是实现路径不同。长度差法是显式地计算长度差让长链表先走几步消除初始偏移双指针交替法是隐式地利用走完自己的路再走别人的路让两个指针的总路程趋于一致最终必然在交点汇合。你可以把双指针法理解为把长度差的处理延迟到了走完一条链表之后——它同样利用了两个链表相交则尾部对齐这个性质。从代码可读性来说长度差法更直白适合新手双指针交替法更精炼适合面试现场手写和追求极致简洁的场景。我个人在面试时会先讲长度差法再主动提出其实还有更简洁的双指针交替法这样既展示了基础理解又展示了优化能力。但在工程代码里我会用带注释的长度差法因为几个月后回头维护代码时双指针那三行要反推一下才能想起来为什么正确。另外双指针交替法有一个隐藏的边界情况需要处理如果 headA 或 headB 本身是 NULL那么循环会直接走到pA ? pA-next : headB这样的逻辑吗不会因为while (pA ! pB)在 pA 和 pB 都为 NULL 时才会退出但如果一个为 NULL 另一个不为 NULL循环会继续。所以在进入循环前最好加一个判断if (!headA || !headB) return NULL;这个判断不是必须的——因为如果 headA 为 NULLpA 为 NULLpB 指向 headB如果非空循环会继续走最终 pB 走到 NULL 后跳到 headA也是 NULL两者相遇退出返回 NULL。但加上这个判断会让逻辑更清晰也更安全避免任何潜在的野指针操作。我建议加上。5. 代码调试笔记我在实际运行中遇到的两个典型问题5.1 问题一忘记重置指针导致看似正确的错误结果有朋友问我为什么自己写的长度差法代码在链表不相交时返回了某个节点地址而不是 NULL。我让他把代码发给我看结果发现他的代码长这样struct ListNode *pA headA; struct ListNode *pB headB; int lenA 0, lenB 0; while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } // 然后直接开始用 pA 和 pB 比较完全忘了把它们重新指向 headA 和 headB问题就在这统计完长度后pA 和 pB 都已经指向 NULL 了。此时再让长的先走、短的同步走实际上操作的是一堆 NULL 指针不仅结果错误还可能在pA-next上触发段错误。这类问题在本地调试时不会立刻崩溃因为对 NULL 指针执行比较操作在语法上是允许的但逻辑就完全错了。我的排查经验是长度统计完成后立刻打印 pA 和 pB 的地址确认它们是 NULL然后再重新赋值。或者更干脆一点用一个独立变量统计长度不要用后续要用的指针变量struct ListNode *cur headA; while (cur) { lenA; cur cur-next; } cur headB; while (cur) { lenB; cur cur-next; }这样 pA 和 pB 从头到尾都保留着初始指向不会因为统计长度而污染。这个习惯不仅适用于这道题所有涉及先遍历一遍统计信息、再从头开始操作的链表题比如寻找中间节点、判断回文链表都适用。5.2 问题二在 LeetCode 上跑出 Time Limit Exceeded 的元凶另一个朋友在 LeetCode 上提交暴力双循环方案遇到超出时间限制。他的链表长度是 10 万级别的O(m * n) 的复杂度在极端情况下要跑 100 亿次比较超时是必然的。这倒不奇怪奇怪的是他在本地测试时完全正常——因为本地的两个链表长度都只有几十个节点。这暴露了一个普遍问题很多初学者在本地测试时喜欢用两个短链表来做验证但这远远不够。链表长度为 1、长度为 0、两个链表完全不相交、两个链表完全重合一个链表是另一个的子集、交点恰好在第一个节点或最后一个节点——这些边界情况全部都要测到。我整理了一个自查用的测试用例清单你可以直接拿去用用例编号headAheadB期望结果1NULLNULLNULL21-2-3NULLNULL31-2-31-2-3相同地址的头节点头节点41-2-34-1-2-3交点在第2个节点值1处节点151-2-34-5不相交NULL61-2-3-42-3-4交点在第2个节点值2处节点2我自己每次写链表题都会准备这样一个 table 驱动的测试而在 LeetCode 上则直接构造对应的测试函数void test() { // 构造链表节点 struct ListNode a1 {1, NULL}, a2 {2, NULL}, c1 {3, NULL}; a1.next a2; a2.next c1; struct ListNode b1 {4, NULL}; b1.next c1; struct ListNode *result getIntersectionNode(a1, b1); printf(Expected c1 address: %p\n, (void*)c1); printf(Actual result: %p\n, (void*)result); }注意测试用例里构造链表时两个链表共用c1节点这正是相交链表的特征。如果你用malloc分别申请两个独立的节点哪怕 val 相同地址也不同测试结果就会偏离相交的定义。5.3 关于内存管理的一个附加提醒这道题在 LeetCode 上做的时候链表节点一般由题目后台分配你不需要自己释放内存。但如果你在本地把链表题改成构造链表 - 判断相交 - 释放链表的完整流程就要格外小心绝对不能对两个链表分别调用 free 来释放共享节点否则同一块内存会被释放两次触发 double free 崩溃。正确做法是先构造一个不含共享节点的两个独立链表做测试或者用一个标志变量记录某个节点是否被释放。我自己在本地调试时通常直接忽略释放这一步只关注算法正确性毕竟题目本身不要求管理内存生命周期。6. 进阶视角这道题延伸出来的链表考点6.1 找到相交节点的变体如果链表有环怎么办相交链表的基础版本假设链表都是无环的。但面试官常会加问如果两个链表可能有环该怎么判断是否相交这个变体其实把问题升级成了判断链表是否有环经典快慢指针题和找环入口Floyd 判圈算法的组合。我的思路是这样先分别检测两个链表是否有环。如果一个有环一个无环那它们不可能相交如果两个都有环相交的情况会更复杂——公共节点可能在环上也可能在环的入口处。处理方式也比较暴力找到两个链表的环入口然后分别走一遍看环上面的节点是否被共享。这个展开讲能再写一篇长文这里点到为止提醒你如果遇到这个追问核心考点依然是指针相等即共享节点这一条。6.2 从 O(m*n) 到 O(mn)复杂度分析是面试考察点面试时即使你写的是正确的长度差法也一定会被要求解释时间复杂度和空间复杂度。这里我建议你把推导清晰地讲出来每个链表最多被完整遍历一遍所以总时间复杂度是 O(m n)只用了常数额外空间所以空间复杂度是 O(1)。如果你写哈希表方案要主动承认它的空间复杂度是 O(m)从而引出后续优化。很多候选人会卡在为什么双指针交替法的空间复杂度是常数这个问题上——因为代码里只有两个指针变量没有额外的数组或哈希表无论链表多长额外内存都不增长。这个结论本身很简单但在面试紧张时容易表述不清建议提前组织好语言。6.3 类似题目横向对比环形链表、回文链表、合并有序链表相交链表不是孤立的题目它和下面几题共享很多底层技巧环形链表LeetCode 141用快慢指针判断是否有环核心是快指针每次走两步慢指针每次走一步如果有环必定相遇。这和相交链表的双指针交替法一样都是利用不同的速度/路线让指针最终汇合的思想。回文链表LeetCode 234先用快慢指针找到中间节点再反转后半部分然后逐节点比较。找中间节点的过程本质上也是利用长度差/同步移动的技巧。合并两个有序链表LeetCode 21这个更多的是考察递归或者迭代式节点拼接但同样强调对 next 指针的精细控制。如果你能把这几题放在一起刷会比孤立刷题效果好得多。因为它们的底层都是一件事理解链表节点的地址唯一性、next 指针的操作边界、以及双指针在链表上的各种应用模式。7. 从会做到做对我的刷题心法总结写到最后分享一点我个人的体会。相交链表这道题我前前后后教过几十个同学写。最让我印象深刻的不是谁一次就写对而是大家普遍会在长度差法和双指针交替法之间选择困难。其实这两者没有优劣之分关键在于你是否能在 30 秒内讲清楚为什么你的代码是正确的。如果你选择了双指针交替法却卡在为什么要跳转到另一个链表头部这个点上面试时反而会露怯。我的建议是平时练习时两种方法都写一遍用同一组测试用例验证。这样你不仅掌握了两种实现还被迫理解了它们的内在一致性。真到了面试或竞赛场上你就能做到手随心动选最顺手的那个。另外还想强调一件事链表这类题目半小时没写出来是正常的。不要灰心不要急着看题解。给自己画图、举例子、推演指针走向这个过程本身就是最大的收获。等你亲手画出那两条指针在链表之间交替跳跃的路线之后你会发现这道题的美感——它用最简单的代码体现了链表结构最本质的性质节点共享、指针即地址、循环即遍历。这种美感是看多少遍题解都体会不到的。## 8. 追问与实践一道题带来的三个自测问题 如果你看完上面这些内容建议先别急着关掉页面。我出三个小问题你能不依赖编译器在心里推演出正确答案才算真正掌握了这道题。 第一问在双指针交替法中如果两个链表长度完全相同且不相交循环会执行多少次才退出我的答案是 2n 次n 为链表长度因为每个指针要走完自己的 n 个节点再走完对方的 n 个节点总共 2n 步后同时到达 NULL。 第二问在长度差法中如果两个链表只有一个公共节点而且这个节点就是 headA 和 headB 本身会发生什么答案是 lenA 和 lenB 相等长度差为 0两个指针从一开始就相等直接返回头节点不需要进入同步循环。 第三问如果把双指针交替法中的 pA pA ? pA-next : headB; 改成 pA pA-next ? pA-next : headB;会发生什么答案是当 pA 指向最后一个非 NULL 节点时pA-next 为 NULL于是 pA 直接跳到 headB跳过了 pA 自己的NULL 状态这个逻辑仍然能在相交链表的场景下工作但在不相交的场景下可能提前退出并返回错误结果。这是一道经典的易错变体建议你亲手推演一遍。 我每次给朋友讲这道题都会把这三个问题抛出去。前两个问题大多数人都能答对第三个问题能立刻答对的人不超过十分之一。为什么因为它考察的不是背代码而是对指针在走完一条链表后的状态变化的完全掌控——这是链表题真正的分水岭。 相交链表只是 C 语言链表大家族里的一个入门关卡。这道题背后藏着指针比较、边界条件、复杂度推导、以及用数学消除不对称性的通用思维。把这些吃透了你再看环形链表、回文链表、合并链表会突然觉得它们之间有千丝万缕的联系。到那时候刷题就真的变成了一件有意思的事。
C语言链表操作精讲：从相交链表到双指针的O(1)解法
## 1. 这道题为什么值得写面试高频与链表操作的试金石 相交链表Intersection of Two Linked Lists在 LeetCode 上是编号 160 的经典题在《剑指 Offer》里对应第 52 题。我见过不少面试官拿它当热身题也见过它作为二面手写题的升级版出现——比如要求不用哈希表、空间复杂度压到 O(1)。这道题表面上看只是找两个链表有没有交点实际上考察的是**链表指针操作的基本功、边界条件的敏感度、以及用数学思维化简问题的能力**。 先说清楚题目本身用一句人话概括就是给你两个单链表的头节点 headA 和 headB判断这两个链表是否在某个节点处汇合如果汇合返回那个相交节点的指针如果不相交返回 NULL。注意一个关键前提——**两个链表一旦相交从相交节点开始后面的所有节点都是共享的**因为它们都是单链表每个节点只有一个 next 指针不可能出现相交之后又分叉的情况。这一点是整个题目所有解法成立的基础。 链表的相交结构长什么样我画个文字版的示意图方便你对着理解A: a1 - a2c1 - c2 - c3 / B: b1 - b2 - b3在这个结构里A 链表从 a1 出发走到 a2 之后进入 c1B 链表从 b1 出发经过 b1、b2、b3 之后也进入 c1。c1 就是相交节点c1、c2、c3 是两个链表共享的部分。注意A 的长度是 4a1、a2、c1、c2、c3一共5个我数错了重来a1、a2、c1、c2、c3是5个节点B 的长度是 5b1、b2、b3、c1、c2、c3但公共部分只有 3 个节点。 为什么说这道题是链表操作的试金石因为链表是 C 语言里最讲究指针的语义的数据结构。写数组题你操作的是一段连续内存、下标直接可算写链表题你手里只有一个指向头节点的指针所有后续节点都要靠 next 一步步走。相交链表这个题目涉及的指针移动、长度差计算、循环退出条件稍有疏忽就会踩空指针的坑。而且 C 语言没有现成的链表库一切都要自己定义结构体、自己管理内存这对指针理解的考察比其他语言更深入。 这篇博文适合正在刷题的在校生、准备面试的求职者也适合工作中偶尔需要手写数据结构的 C 语言开发者。我会从最朴素的做法开始逐步讲到最优解再附上我实际调试过程中踩过的坑和排查经验。 ## 2. 先搞定最容易想到的方案哈希表与暴力双循环 ### 2.1 哈希表方案思路最直但空间换时间 最简单的思路是这样既然相交链表从交点开始共享节点那我只要把一个链表的所有节点地址记下来然后遍历另一个链表逐个检查当前节点的地址是否在刚才的记录里。如果在那这个节点就是交点如果走完都没找到说明两个链表不相交。 C 语言实现这个方案可以用哈希表也可以用借用数组当标记的办法——但注意这里存的是**指针地址**不是整数值所以直接用数组下标做哈希的话你得把指针转换为整数再哈希。我这里的示例代码用了一个简单的哈希结构你也可以直接用带哨兵的双重循环先跑通功能。 c #include stdio.h #include stdlib.h struct ListNode { int val; struct ListNode *next; }; #define HASH_SIZE 1024 struct HashNode { struct ListNode *addr; struct ListNode *next; // 链地址法解决冲突 }; struct HashNode *hash_table[HASH_SIZE]; unsigned int hash_ptr(struct ListNode *p) { return ((unsigned long)p 4) % HASH_SIZE; } void hash_insert(struct ListNode *p) { unsigned int idx hash_ptr(p); struct HashNode *node (struct HashNode *)malloc(sizeof(struct HashNode)); node-addr p; node-next hash_table[idx]; hash_table[idx] node; } int hash_find(struct ListNode *p) { unsigned int idx hash_ptr(p); struct HashNode *cur hash_table[idx]; while (cur) { if (cur-addr p) return 1; cur cur-next; } return 0; } struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { for (int i 0; i HASH_SIZE; i) hash_table[i] NULL; // 每次调用前清空 struct ListNode *p headA; while (p) { hash_insert(p); p p-next; } p headB; while (p) { if (hash_find(p)) return p; p p-next; } return NULL; }这个方案的时间复杂度是 O(m n)其中 m 和 n 分别是两个链表的长度因为遍历一次 A 链表做插入遍历一次 B 链表做查找。空间复杂度是 O(m)因为需要把 A 链表的所有节点地址存下来。这个方案在面试时可以作为我第一时间想到的解法说出来但通常面试官会接着问一句能不能把空间复杂度降到 O(1)这就是下面两个方案的出场时机了。2.2 暴力双循环最笨但最容易验证思路如果不想引入哈希表另一个直观方案是双循环对 A 链表的每个节点都完整遍历一遍 B 链表检查有没有指针相等的节点。伪代码如下struct ListNode *pA headA; while (pA) { struct ListNode *pB headB; while (pB) { if (pA pB) return pA; pB pB-next; } pA pA-next; } return NULL;这个写法最直白时间复杂度是 O(m * n)空间复杂度是 O(1)。它的优点是不容易写错尤其适合你在本地快速验证两个链表到底相不相交、交点在哪这个事实。但它的缺点很明显一旦链表长度上万性能就会急剧下降。我个人的建议是如果你在面试中先说哈希表方案再优化到双指针方案完全没有必要再提暴力双循环。但如果你是在自己学习调试阶段暴力双循环是很好的辅助验证工具——你可以用它跑一遍测试用例确认自己的预期结果再去改写成更优的方案。2.3 为什么哈希表方案在 C 语言里要特别小心这里必须提醒一个 C 语言特有的坑哈希表的键是指针值而不是节点里的 val。我见过不少人刚上手这道题时想用节点值 val 作为比较依据结果两个链表里有两个值相同的节点但它们的地址完全不同就被误判成相交了。链表相交判断的本质是判断节点是否同一个不是判断值是否相等。另外哈希表方案里如果你用(unsigned long)p 4做哈希是把指针右移 4 位因为典型的链表节点通过 malloc 分配时地址通常按 16 字节对齐低位基本为 0右移后哈希分布更均匀。这个技巧在嵌入式或者教学场景下能提升一点性能但不必过度优化。真正在工程里我更倾向于直接用双指针方案省去所有哈希表内存管理的麻烦。3. 高效解法一长度差法先对齐再同步走3.1 核心思想把长度差这个变量消掉哈希表和暴力法的本质问题在于两个链表长度不等时你没法简单地让两个指针同步往前走。但如果我们换个角度看如果两个链表相交那么从交点到尾部的公共部分长度是相同的。因此两个链表的长度差必然完全来自交点之前的独有部分。这么说可能有点绕我举一个例子。假设 A 链表长度为 7B 链表长度为 5交点位于 A 的第 3 个节点、B 的第 1 个节点。那么A 的独有部分长度 3 - 1 2a1、a2B 的独有部分长度 1 - 1 0公共部分长度 5 - 1 1不对我重新算一下。公共部分是从交点开始到尾部这个长度对两个链表是一样的。如果 A 总长 7交点前有 2 个独有节点那交点后的公共长度就是 7 - 2 - 1交点头本身其实不用这么纠结关键结论只有一个两个链表的长度差就等于两个指针各自走到交点所需步数的差。如果能让两个指针从距离交点相同步数的位置出发那么它们同步前进必然会在交点相遇。长度差法的具体操作分三步分别遍历两个链表得到长度 lenA 和 lenB。让较长的链表先走abs(lenA - lenB)步这样两个指针就处在距离链表末尾相同距离的位置。然后两个指针同步前进每走一步比较一次相等则返回该节点走到 NULL 都没相遇说明不相交。3.2 C 语言完整实现与测试直接上代码struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { int lenA 0, lenB 0; struct ListNode *pA headA, *pB headB; // 第一遍统计两个链表的长度 while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } // 重新指向头节点 pA headA; pB headB; // 让较长的链表先走长度差 int diff lenA - lenB; if (diff 0) { while (diff--) pA pA-next; } else { diff -diff; while (diff--) pB pB-next; } // 同步前进比较指针地址 while (pA pB) { if (pA pB) return pA; pA pA-next; pB pB-next; } return NULL; }我在本地跑了几组测试第一组两个链表不相交headA: 1 - 2 - 3 headB: 4 - 5 - 6 期望结果NULL运行过程lenA3lenB3长度差为 0两个指针从头同步走走到 NULL 都没有相等返回 NULL。正确。第二组两个链表相交headA: 1 - 2 - 3 - 4 - 5 headB: 6 - 3 - 4 - 5 交点值 3假设地址相同 期望结果返回值为 3 的节点指针运行过程lenA5lenB4diff1pA 先走一步来到指向 2 的节点。此时 pA 距离交点节点 3还有 1 步pB 距离交点节点 6 的下一个也就是节点 3也是 1 步。然后同步走pA 到节点 3pB 也到节点 3地址相等返回。正确。3.3 这个方案的边界条件与常见错误写这个代码时最容易犯的错误有三个我一个个说。第一个错误统计长度后忘记把指针重置回头节点。这几乎是每个初学者都会踩的坑。两个 while 循环走完之后pA 和 pB 都已经指向 NULL 了如果不重新赋值pA headA; pB headB;后面的逻辑全部白写。第二个错误处理长度差时符号搞反。如果 lenA lenB你让 pA 先走 diff 步反之让 pB 走。这个 if-else 分支本身不难但如果你写到一半改动了变量的含义很容易把diff -diff的逻辑丢掉导致指针越界。我建议先写一个int diff lenA - lenB;然后统一处理比如if (diff 0) { while (diff) pB pB-next; } else { while (diff--) pA pA-next; }这里注意diff为负时diff是将负数逐步增加直到 0效果正好是让 pB 先走-diff步。这个写法在 C 语言里完全合法但读代码的人需要想一下注释写清楚比较好。第三个错误同步前进时只判断 val 相等而不是地址相等。我在前面已经强调过了pA-val pB-val只能说明两个节点的值相同不能说明它们相交。必须判断pA pB这是指针比较比较的才是地址。长度差法的时间复杂度是 O(m n)空间复杂度 O(1)已经能满足绝大多数面试要求了。但 LeetCode 的官方题解还给出了更巧妙的双指针法——两个指针走对方的路连长度差都不用先算。这就是下一节的内容。4. 高效解法二双指针交替法最优雅的 O(1) 方案4.1 为什么两个指针走完各自的路再走对方的路就能相遇这个解法的代码极短但理解起来需要绕一个弯。我先给出代码再解释原理。struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (!headA || !headB) return NULL; struct ListNode *pA headA; struct ListNode *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }就这么几行。我第一次看到这个解法时愣了一下因为它的逻辑太绕了——两个指针都不停地走走到 NULL 就跳到另一个链表的头部直到它们相遇。但仔细推演之后发现这实际上是长度差法的另一种表达而且连算长度这个步骤都省了。假设链表 A 长度为 m链表 B 长度为 n交点前的独有部分分别为 a 和 b公共部分长度为 c。那么m a cn b c当 pA 走完 A 链表走了 m 步时它会跳到 headB 继续走当 pB 走完 B 链表走了 n 步时它会跳到 headA 继续走。如果两个链表相交pA 一共走m b步后pB 一共走n a步后它们都会到达交点。我们来验证这个步数一致性pA 走到交点需要的总步数 A 链表独有部分 a 公共部分 c不对这里要重新算。pA 从 headA 出发走到 A 链表的交点需要 a 1 步不对我不用步数精确到个位只看相对关系。更简洁的理解方式是这样pA 总共走过的路径是A 链表全部 B 链表交点之前的独有部分也就是m bpB 总共走过的路径是B 链表全部 A 链表交点之前的独有部分也就是n a。由于m b (a c) b a b c n a (b c) a a b c所以当 pA 走完m b步、pB 走完n a步时它们走过的总步数相同而且此时它们都正好站在交点上。这就是殊途同归。如果两个链表不相交那么 pA 走完m n步、pB 也走完n m步后它们会同时走到 NULL即pA pB NULL循环退出返回 NULL。4.2 逐步推演用一个具体例子走一遍纸上得来终觉浅我手动推演一遍。假设 A 链表a1 - a2 - c1 - c2 - NULLB 链表b1 - b2 - b3 - c1 - c2 - NULL。交点 c1。初始化pA 指向 a1pB 指向 b1。第 1 步循环pA ! pBpA 指向 a2pB 指向 b2。 第 2 步循环pA ! pBpA 指向 c1pB 指向 b3。 第 3 步循环pA ! pBpA 指向 c2pB 指向 c1。 第 4 步循环pA ! pBpA 向后走此时 pA 在 c2 的 next也就是 NULLpB 从 c1 走到 c2。根据代码逻辑pA 为 NULL所以 pA 被赋值为 headB即 b1pB 不为 NULL所以 pB 指向 c2。第 5 步循环pA现在指向 b1! pB指向 c2pA 走到 b2pB 走到 NULL于是 pB 被赋值为 headA即 a1。 第 6 步循环pA 指向 b2pB 指向 a1不相等pA 走到 b3pB 走到 a2。 第 7 步循环pA 指向 b3pB 指向 a2不相等pA 走到 c1pB 走到 c1。 第 8 步循环pA pB跳出循环返回 c1。从第 1 步到第 8 步pA 实际遍历了 A 的全部 4 个节点又遍历了 B 靠近交点之前的独有部分 b1、b2、b3pB 遍历了 B 的全部 5 个节点又遍历了 A 靠近交点之前的独有部分 a1、a2。两者最终在 c1 相遇。看起来很神奇其实就是前面证明的恒等式在起作用。4.3 这个解法与长度差法的本质联系很多人会问双指针交替法和长度差法到底哪个更好我的答案是它们在数学上是等价的只是实现路径不同。长度差法是显式地计算长度差让长链表先走几步消除初始偏移双指针交替法是隐式地利用走完自己的路再走别人的路让两个指针的总路程趋于一致最终必然在交点汇合。你可以把双指针法理解为把长度差的处理延迟到了走完一条链表之后——它同样利用了两个链表相交则尾部对齐这个性质。从代码可读性来说长度差法更直白适合新手双指针交替法更精炼适合面试现场手写和追求极致简洁的场景。我个人在面试时会先讲长度差法再主动提出其实还有更简洁的双指针交替法这样既展示了基础理解又展示了优化能力。但在工程代码里我会用带注释的长度差法因为几个月后回头维护代码时双指针那三行要反推一下才能想起来为什么正确。另外双指针交替法有一个隐藏的边界情况需要处理如果 headA 或 headB 本身是 NULL那么循环会直接走到pA ? pA-next : headB这样的逻辑吗不会因为while (pA ! pB)在 pA 和 pB 都为 NULL 时才会退出但如果一个为 NULL 另一个不为 NULL循环会继续。所以在进入循环前最好加一个判断if (!headA || !headB) return NULL;这个判断不是必须的——因为如果 headA 为 NULLpA 为 NULLpB 指向 headB如果非空循环会继续走最终 pB 走到 NULL 后跳到 headA也是 NULL两者相遇退出返回 NULL。但加上这个判断会让逻辑更清晰也更安全避免任何潜在的野指针操作。我建议加上。5. 代码调试笔记我在实际运行中遇到的两个典型问题5.1 问题一忘记重置指针导致看似正确的错误结果有朋友问我为什么自己写的长度差法代码在链表不相交时返回了某个节点地址而不是 NULL。我让他把代码发给我看结果发现他的代码长这样struct ListNode *pA headA; struct ListNode *pB headB; int lenA 0, lenB 0; while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } // 然后直接开始用 pA 和 pB 比较完全忘了把它们重新指向 headA 和 headB问题就在这统计完长度后pA 和 pB 都已经指向 NULL 了。此时再让长的先走、短的同步走实际上操作的是一堆 NULL 指针不仅结果错误还可能在pA-next上触发段错误。这类问题在本地调试时不会立刻崩溃因为对 NULL 指针执行比较操作在语法上是允许的但逻辑就完全错了。我的排查经验是长度统计完成后立刻打印 pA 和 pB 的地址确认它们是 NULL然后再重新赋值。或者更干脆一点用一个独立变量统计长度不要用后续要用的指针变量struct ListNode *cur headA; while (cur) { lenA; cur cur-next; } cur headB; while (cur) { lenB; cur cur-next; }这样 pA 和 pB 从头到尾都保留着初始指向不会因为统计长度而污染。这个习惯不仅适用于这道题所有涉及先遍历一遍统计信息、再从头开始操作的链表题比如寻找中间节点、判断回文链表都适用。5.2 问题二在 LeetCode 上跑出 Time Limit Exceeded 的元凶另一个朋友在 LeetCode 上提交暴力双循环方案遇到超出时间限制。他的链表长度是 10 万级别的O(m * n) 的复杂度在极端情况下要跑 100 亿次比较超时是必然的。这倒不奇怪奇怪的是他在本地测试时完全正常——因为本地的两个链表长度都只有几十个节点。这暴露了一个普遍问题很多初学者在本地测试时喜欢用两个短链表来做验证但这远远不够。链表长度为 1、长度为 0、两个链表完全不相交、两个链表完全重合一个链表是另一个的子集、交点恰好在第一个节点或最后一个节点——这些边界情况全部都要测到。我整理了一个自查用的测试用例清单你可以直接拿去用用例编号headAheadB期望结果1NULLNULLNULL21-2-3NULLNULL31-2-31-2-3相同地址的头节点头节点41-2-34-1-2-3交点在第2个节点值1处节点151-2-34-5不相交NULL61-2-3-42-3-4交点在第2个节点值2处节点2我自己每次写链表题都会准备这样一个 table 驱动的测试而在 LeetCode 上则直接构造对应的测试函数void test() { // 构造链表节点 struct ListNode a1 {1, NULL}, a2 {2, NULL}, c1 {3, NULL}; a1.next a2; a2.next c1; struct ListNode b1 {4, NULL}; b1.next c1; struct ListNode *result getIntersectionNode(a1, b1); printf(Expected c1 address: %p\n, (void*)c1); printf(Actual result: %p\n, (void*)result); }注意测试用例里构造链表时两个链表共用c1节点这正是相交链表的特征。如果你用malloc分别申请两个独立的节点哪怕 val 相同地址也不同测试结果就会偏离相交的定义。5.3 关于内存管理的一个附加提醒这道题在 LeetCode 上做的时候链表节点一般由题目后台分配你不需要自己释放内存。但如果你在本地把链表题改成构造链表 - 判断相交 - 释放链表的完整流程就要格外小心绝对不能对两个链表分别调用 free 来释放共享节点否则同一块内存会被释放两次触发 double free 崩溃。正确做法是先构造一个不含共享节点的两个独立链表做测试或者用一个标志变量记录某个节点是否被释放。我自己在本地调试时通常直接忽略释放这一步只关注算法正确性毕竟题目本身不要求管理内存生命周期。6. 进阶视角这道题延伸出来的链表考点6.1 找到相交节点的变体如果链表有环怎么办相交链表的基础版本假设链表都是无环的。但面试官常会加问如果两个链表可能有环该怎么判断是否相交这个变体其实把问题升级成了判断链表是否有环经典快慢指针题和找环入口Floyd 判圈算法的组合。我的思路是这样先分别检测两个链表是否有环。如果一个有环一个无环那它们不可能相交如果两个都有环相交的情况会更复杂——公共节点可能在环上也可能在环的入口处。处理方式也比较暴力找到两个链表的环入口然后分别走一遍看环上面的节点是否被共享。这个展开讲能再写一篇长文这里点到为止提醒你如果遇到这个追问核心考点依然是指针相等即共享节点这一条。6.2 从 O(m*n) 到 O(mn)复杂度分析是面试考察点面试时即使你写的是正确的长度差法也一定会被要求解释时间复杂度和空间复杂度。这里我建议你把推导清晰地讲出来每个链表最多被完整遍历一遍所以总时间复杂度是 O(m n)只用了常数额外空间所以空间复杂度是 O(1)。如果你写哈希表方案要主动承认它的空间复杂度是 O(m)从而引出后续优化。很多候选人会卡在为什么双指针交替法的空间复杂度是常数这个问题上——因为代码里只有两个指针变量没有额外的数组或哈希表无论链表多长额外内存都不增长。这个结论本身很简单但在面试紧张时容易表述不清建议提前组织好语言。6.3 类似题目横向对比环形链表、回文链表、合并有序链表相交链表不是孤立的题目它和下面几题共享很多底层技巧环形链表LeetCode 141用快慢指针判断是否有环核心是快指针每次走两步慢指针每次走一步如果有环必定相遇。这和相交链表的双指针交替法一样都是利用不同的速度/路线让指针最终汇合的思想。回文链表LeetCode 234先用快慢指针找到中间节点再反转后半部分然后逐节点比较。找中间节点的过程本质上也是利用长度差/同步移动的技巧。合并两个有序链表LeetCode 21这个更多的是考察递归或者迭代式节点拼接但同样强调对 next 指针的精细控制。如果你能把这几题放在一起刷会比孤立刷题效果好得多。因为它们的底层都是一件事理解链表节点的地址唯一性、next 指针的操作边界、以及双指针在链表上的各种应用模式。7. 从会做到做对我的刷题心法总结写到最后分享一点我个人的体会。相交链表这道题我前前后后教过几十个同学写。最让我印象深刻的不是谁一次就写对而是大家普遍会在长度差法和双指针交替法之间选择困难。其实这两者没有优劣之分关键在于你是否能在 30 秒内讲清楚为什么你的代码是正确的。如果你选择了双指针交替法却卡在为什么要跳转到另一个链表头部这个点上面试时反而会露怯。我的建议是平时练习时两种方法都写一遍用同一组测试用例验证。这样你不仅掌握了两种实现还被迫理解了它们的内在一致性。真到了面试或竞赛场上你就能做到手随心动选最顺手的那个。另外还想强调一件事链表这类题目半小时没写出来是正常的。不要灰心不要急着看题解。给自己画图、举例子、推演指针走向这个过程本身就是最大的收获。等你亲手画出那两条指针在链表之间交替跳跃的路线之后你会发现这道题的美感——它用最简单的代码体现了链表结构最本质的性质节点共享、指针即地址、循环即遍历。这种美感是看多少遍题解都体会不到的。## 8. 追问与实践一道题带来的三个自测问题 如果你看完上面这些内容建议先别急着关掉页面。我出三个小问题你能不依赖编译器在心里推演出正确答案才算真正掌握了这道题。 第一问在双指针交替法中如果两个链表长度完全相同且不相交循环会执行多少次才退出我的答案是 2n 次n 为链表长度因为每个指针要走完自己的 n 个节点再走完对方的 n 个节点总共 2n 步后同时到达 NULL。 第二问在长度差法中如果两个链表只有一个公共节点而且这个节点就是 headA 和 headB 本身会发生什么答案是 lenA 和 lenB 相等长度差为 0两个指针从一开始就相等直接返回头节点不需要进入同步循环。 第三问如果把双指针交替法中的 pA pA ? pA-next : headB; 改成 pA pA-next ? pA-next : headB;会发生什么答案是当 pA 指向最后一个非 NULL 节点时pA-next 为 NULL于是 pA 直接跳到 headB跳过了 pA 自己的NULL 状态这个逻辑仍然能在相交链表的场景下工作但在不相交的场景下可能提前退出并返回错误结果。这是一道经典的易错变体建议你亲手推演一遍。 我每次给朋友讲这道题都会把这三个问题抛出去。前两个问题大多数人都能答对第三个问题能立刻答对的人不超过十分之一。为什么因为它考察的不是背代码而是对指针在走完一条链表后的状态变化的完全掌控——这是链表题真正的分水岭。 相交链表只是 C 语言链表大家族里的一个入门关卡。这道题背后藏着指针比较、边界条件、复杂度推导、以及用数学消除不对称性的通用思维。把这些吃透了你再看环形链表、回文链表、合并链表会突然觉得它们之间有千丝万缕的联系。到那时候刷题就真的变成了一件有意思的事。
