回文链表与相交链表：快慢指针与双指针的经典解法

1. 为什么把回文和相交放在一起两把链表的“钥匙”我在帮部门做技术面试的时候最喜欢在链表环节问两道题一道叫回文链表一道叫相交链表。这两道题放在一起并不是“难度递进”这么简单而是它们分别代表了链表题里两种最典型的思维路径回文链表考的是“你知不知道怎么在单链表上找到中点并反转一部分”相交链表考的是**“你愿不愿意跳出链表本身的直觉去构建一个等量关系”**。只要把这两道题吃透链表这块的基本功就稳了一大半。先说回文链表。题目本身很简单给定一个单链表的头节点判断它是不是回文链表。所谓回文就是正着读和倒着读一样比如1 - 2 - 2 - 1是回文1 - 2 - 3 - 2 - 1也是回文但1 - 2 - 3就不是。很多初学者第一反应是把链表转成数组然后两边往中间比。这个思路没有错逻辑上完全成立空间复杂度却是 O(n)。面试官要是追问一句“能不能不用额外空间”很多人就卡住了。这道题真正的考点就是在不占用 O(n) 额外空间的前提下完成判断这需要你掌握两个基础操作快慢指针找中点、单链表反转。相交链表也很有意思。题目是这样的有两个单链表它们可能在某个节点之后完全重合请你找出两个链表相交的起始节点。没接触过的人第一反应往往是“暴力”拿链表 A 的每个节点去链表 B 里找时间复杂度 O(m * n)效率极低。稍微有点经验的人会想到用哈希表把 A 的节点存下来然后遍历 B查第一个出现在哈希表里的节点时间复杂度降到了 O(m n)但空间复杂度是 O(n)。这两道题放在一起讲是因为它们都指向同一个真相链表的很多经典问题最优解都藏在“如何用有限的指针变量在链表上游走出一个漂亮的规律”里而不是依赖额外存储。这篇文章适合谁你是刚学数据结构的学生想把“链表”这个章节真正弄懂或者你在准备面试需要一套能现场写出来、讲清楚思路的解法再或者你只是想把代码写得干净利落减少边界 bug——那这篇内容都值得你花上二十分钟慢慢读。我会把每一步“为什么这样做”都讲透而不是只丢给你一个能跑通的答案。另外本文所有代码用 C 语言写逻辑上你换成 C、Java、Python 都毫无障碍。2. 回文链表三步走的经典解法2.1 快慢指针把中点“算”出来回文判断的核心困难在于单链表只能从头往后走不能回头。你想把前半段和后半段逐位对比就必须找一个办法让后半段也能“从后往前”被访问。既然不能回头那我们就主动“再造一个反向的链表”把后半段反转过来。第一步找到链表的中间节点。这里用的就是快慢指针slow每次走一步fast每次走两步。当fast走到链表末尾的时候slow正好停在中间位置。你可能会问为什么快指针要走两步走三步行不行其实走三步也行但快慢指针的步数差越大慢指针的位置越难精确控制而且“两步差”可以用最简单的 while 条件写清楚。工程上永远选最容易验证的方案。关于这个 while 条件我见过不少人在fast-next fast-next-next和fast fast-next之间纠结。实践下来用while (fast fast-next)最省心。链表长度为奇数时slow会停在正中间那个节点长度为偶数时slow会停在两个中间节点的后一个也就是后半段的开头。这两种落点对回文判断都很友好。struct ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; }这段代码跑完slow指向的就是后半段的起始节点。这一步是整个解法里最容易被忽视的地方很多人不是不会写快慢指针而是没想清楚 slow 最终落在哪里导致后面反转起点错一位。2.2 反转后半段再逐点对齐拿到slow之后第二步就是把slow开头的那段链表原地反转。单链表反转是一个基本功三指针迭代法是最稳的写法不会像递归那样容易爆栈也比较容易边写边解释。struct ListNode *reverseList(struct ListNode *head) { struct ListNode *prev NULL, *cur head; while (cur) { struct ListNode *next cur-next; cur-next prev; prev cur; cur next; } return prev; }这里我多说一句很多教材喜欢用pre、p、q这种命名但变量名真的不必太省。prev、cur、next写清楚调 bug 的时候能省一半时间。反转完成后reverseList(slow)返回新的头节点这个头节点在原链表里位于最后一个位置但它反转后变成后半段的“头”。第三步就很简单了拿一个指针p指向原链表head另一个指针q指向反转后的后半段头节点依次比较p-val和q-val。只要出现不相等直接返回 false如果一路比完说明是回文返回 true。bool isPalindrome(struct ListNode *head) { if (!head || !head-next) return true; struct ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } struct ListNode *half reverseList(slow); struct ListNode *p head, *q half; while (q) { if (p-val ! q-val) return false; p p-next; q q-next; } return true; }这里有个细节值得展开一下奇数长度时slow停在正中间反转之后q指向的链表里其实包含了原来的中间节点。比如1 - 2 - 3 - 2 - 1slow在3反转3 - 2 - 1得到1 - 2 - 3。接下来p从原链表的1开始q从反转后的1开始一路比到3和3相等循环结束。你会发现中间节点和自己比了一次这完全不影响结果反而让逻辑更统一——你不需要单独区分奇偶情况。2.3 完整代码与复杂度说明把上面三段拼起来就是一道完整的回文链表解法。有些读者可能会问while (q)和while (p q)有什么区别在这个场景里p和q的“剩余长度”在大多数情况下是一样的奇数时p比q多一个节点所以只判断q不为空就够了。但如果你为了稳写成while (p q)也完全正确。我自己写的话倾向于while (q)因为一旦某个值不相等早就返回了能走到循环末尾说明前半段和后半段已经完美匹配。这段解法的时间复杂度是 O(n)空间复杂度是 O(1)。对比数组法的 O(n) 空间优势非常明显。尤其当链表有几百万个节点的时候开数组和不开数组的差距是质的区别。我还想补一个“要不要恢复链表”的问题。很多题解在判断完之后不会恢复链表LeetCode 官方也没有强制要求。但如果你在真实工程环境里写代码或者面试官多问一句“你的函数会不会改变传入的链表结构”你就应该知道反转操作确实把原链表的后半段方向改掉了。如果想保持函数无副作用可以在返回前再把后半段反转回来代码就是再调一次reverseList(half)让链表恢复原样。这种习惯看起来小却是区分“能写对”和“写得好”的分水岭。3. 相交链表双指针轮换背后的长度等式3.1 先排除“记路径”的笨办法相交链表题的题干通常长这样给你两个单链表headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回NULL。题目还强调了一点不能破坏原始链表结构。这个概念很多初学者会误解以为相交是两个链表在某个节点“碰了一下”然后各自分开。其实不是两个链表一旦相交从交点开始后面的所有节点都是共享的形成一个 Y 字形。为什么会这样因为单链表的每个节点只有一个next指针一个节点不可能同时有两个后继所以两条链表一旦在某个节点合并后面就只能是一条路走到黑。理解了这一点你就能明白为什么暴力法那么傻拿 A 的每个节点去 B 里一遍遍查明明两个链表后半段完全相同你却要把相同的节点比无数次。哈希表法稍微好一点先把 A 的所有节点地址存进一个集合再遍历 B第一次在集合里命中的节点就是交点。这个做法写起来快但空间复杂度 O(n)面试官如果不满意大概率会接着问你“能不能只用 O(1) 空间”。3.2 双指针交替为什么一定能相遇O(1) 空间的正解是双指针交替法代码短到不可思议但理解起来需要一点抽象思维。先说思路两个指针pA、pB分别从headA、headB出发同步往后走。当pA走到链表 A 的末尾时让它跳到headB继续走当pB走到链表 B 的末尾时让它跳到headA继续走。如果两个链表相交这两个指针一定会在交点相遇如果不相交它们会同时走到NULL。struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (!headA || !headB) return NULL; struct ListNode *pA headA, *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }这段代码我第一次看的时候觉得像魔术凭什么它俩一定相遇后来我把长度等式写出来就全明白了。假设链表 A 的非公共部分长度为a链表 B 的非公共部分长度为b公共部分长度为c。那么链表 A 总长是a c链表 B 总长是b c。pA走完自己的 A 之后接着走 B 的b步就能到达交点总步数是a c bpB走完自己的 B 之后接着走 A 的a步同样能到达交点总步数是b c a。这两个数相等所以它们会在同一时刻站在同一个节点上。如果没有交点情况更简单pA走完 A 再走完 B总步数a bpB走完 B 再走完 A总步数b a。两个指针最终同时走到NULL此时pA pB NULL循环退出返回NULL。这就是为什么 while 条件只写pA ! pB不需要额外加pA pB的判断——无交点时它们会用“都是 NULL”的方式自然相等。3.3 和“长度对齐法”做个对比很多教材里还会介绍另一种做法叫长度对齐法先分别算出两个链表的长度让较长的链表先走长度差然后两个指针同步走第一个相等的节点就是交点。这个思路更直观很像跑步比赛里“让内道选手退后一点再同时起跑”。那为什么我更推荐双指针交替法三个原因。第一代码短状态少不容易写出边界 bug。第二它不需要额外遍历一次链表来算长度虽然时间复杂度都是 O(n)但常数更小。第三这种“交换跑道”的思路可以迁移到其他题目比如后面要讲的环形链表变体。我把两种方法的特点整理成了一个表格方便你做选择方法核心思想时间复杂度空间复杂度代码量上手难度暴力法双重循环逐个比较O(m * n)O(1)短低哈希表法存储 A 的节点地址遍历 B 查重O(m n)O(n)短低长度对齐法算出长度差长链表先走O(m n)O(1)中中双指针交替法走完自己的链表后换到对方链表O(m n)O(1)极短中高如果你正在准备考试长度对齐法更容易向别人解释清楚如果你在面试现场双指针交替法会显得你对链表理解更深。两道方法我都建议能手写出来因为面试官可能会让你“先讲思路再写代码”能同时掌握两种你就占据了主动。4. 面试和作业里最容易翻车的边界以及我踩过的坑4.1 空链表、单节点、奇偶长度的处理代码写得对只是第一步边界条件才是真正拉开差距的地方。先说空链表。isPalindrome(NULL)应该返回什么按定义空链表没有元素它天然满足“正着读倒着读一样”应该返回 true。getIntersectionNode(NULL, headB)呢一个链表为空不可能有交点返回 NULL。这两个判断写在前两行既保护了后面的空指针访问也是在向阅读代码的人表明你考虑过边界。单节点链表是另一个经典陷阱。head-next NULL时回文判断直接返回 true 是没问题的。相交链表不存在单节点特判因为算法本身能处理但如果你习惯了在某些题里特判单节点也要注意不要顺手写错。我自己见过最典型的错误是判断完head非空就直接访问head-next-next结果在单节点链表上直接把程序干崩溃了。奇偶长度的影响在前文已经提过这里再做一个总结快慢指针循环结束时如果链表长度是奇数slow在正中间偶数slow在后半段的第一个节点。这两种情况下反转后半段再进行对比都不需要额外特判。你要是发现哪里对比结果不对先别急着怀疑算法花一分钟画一个1 - 2 - 3 - 2 - 1的图把slow的位置标出来问题马上就清楚了。4.2 反转破坏原始结构的问题写回文链表时我见过不少同学在“反转后半段”这一步之后继续用head去遍历链表结果发现链表结构变了怎么想都想不通。原因是reverseList(slow)是原地反转它把slow开始的这一段所有节点的next指针方向都改掉了原链表从中间被“撕开”了。这件事本身不是 bug因为我们后续比对的逻辑就是基于“反转后的后半段”设计的。但如果你还想在判断完以后做别的事比如再遍历一次原链表那就必须先恢复。恢复的方法很简单在isPalindrome返回前再调用一次reverseList(half)。注意这时候half还是后半段反转后的头节点对它再反转一次后半段就恢复成原来的顺序整条链表重新连成完整的一条。我自己的习惯是除非题目明确允许修改链表否则我写的函数最好对传入数据保持零副作用。面试的时候主动指出“这个解法会在判断后恢复链表”通常是一个加分项。4.3 自己造测试数据时容易忽略的细节学习阶段很多人的测试方式就是在 main 函数里手动建一个链表调一下函数看一眼结果。这件事本身没错但我在带新人的时候发现他们造数据时经常只造“标准情况”比如回文链表只造一个偶数长度、相交链表只造一个交点居中的用例。真实情况远比这复杂。相交链表造数据时有个特别容易踩的坑你以为把两个指针指向同一个数值的节点就是“相交”了实际上链表相交是地址层面的共享。你必须真正让两个链表的某个节点是同一个malloc出来的节点相交判断才成立。如果你只是在两个链表里分别造了一个值为 3 的节点它们虽然值相等、地址不同但算法会正确地返回 NULL。很多初学者拿这种“假相交”数据测试然后对着 NULL 的结果发呆。回文链表造数据时我建议至少测这五种空链表、单节点、偶数长度回文、奇数长度回文、偶数长度非回文。相交链表则至少测无交点、交点在第一个节点两个链表完全共用一个头、交点在中间、一个链表完全包含在另一个链表里。把这些用例跑一遍你的代码基本就站稳了。5. 从这两题延伸到整个链表题型的通用思维5.1 快慢指针的泛化应用回文链表里的快慢指针只是一个开始。快慢指针这个套路在链表题里几乎是万金油找链表中点、判断链表是否有环、找到环的入口、找链表倒数第 k 个节点通通可以用它解决。判断链表是否有环是一个经典例子。slow每次走一步fast每次走两步如果有环两者必然相遇如果没环fast会先一步碰到NULL。这个“必然相遇”的直觉和相交链表很像本质上是相对速度的差异——fast相对于slow每轮只靠近一步所以不会跳过。找环入口则是在相遇后把一个指针挪回head两个指针都每次走一步再次相遇的点就是入口这一步的推导过程和相交链表的长度等式如出一辙。所以你会发现链表题里所谓的“新题”很多都是旧技巧的组合或者变形。你在回文链表里练熟的中点查找直接迁移到“找链表中点”就是一道独立的题你在这里练熟的单链表反转迁移到“反转链表 II”就是指定区间反转。熟练之后面试官抛出一个链表题你脑子里应该立刻出现一个“工具箱”快慢指针、双指针、反转、合并、删除、倒数第 k 个……然后根据题目条件从中挑选合适的工具组合。5.2 双指针等量代换的泛化应用相交链表的核心是构造一个等量关系a c b b c a。这种“两个指针分别走两条路径总路程相等”的思路放到环形链表里也成立。拿“寻找重复数”这道题来说数组里的值可以映射成一张隐式链表快慢指针能找到“环”的入口也就是重复出现的数字。这和相交链表共享同一个数学模型只是把链表从显式结构变成了隐式结构。另一个例子是“两个链表相加”两个指针同时从各自的链表头出发用一个变量记录进位逐位相加这又是双指针同步遍历的典型用法。我总结过一条经验链表题里只要题目出现“寻找某个特定位置”“判断是否存在某种关系”优先思考能不能用两个指针制造一条“路径差”。这个思维模式一旦建立你会发现很多难题的解答也不过是几行代码难的只是你愿不愿意跳出“拿数组 / 哈希表硬存”的舒适区。5.3 链表的工程价值不该被轻视有人可能会说我以后写业务代码又不天天操作链表学这么细干嘛这个想法能理解但不太对。链表的物理结构可能不常直接出现在企业应用里但它背后的指针操作、边界处理、空间时间权衡是每一层技术栈都要面对的基础问题。拿缓存淘汰算法 LRU 来说经典实现就是“哈希表 双向链表”哈希表负责 O(1) 查找链表负责 O(1) 插入和删除。你如果只会用数组模拟每次淘汰都要移动大量元素性能立刻崩。再比如内核里的大量链表操作文件系统的空闲块管理哪一样离得开链表的基础功退一步讲即便你只写业务代码理解链表也能帮你更好地理解队列、栈、图这些更复杂的数据结构。数据结构排在第一课叫“数据结构”不是因为它简单而是因为它是后面所有复杂内容的基石。我在学习阶段有一个体会很多题目看着难拆开看不过是“快慢指针 反转”或者“双指针 等量代换”的组合。这两道题我建议你不光要会写还要能脱离代码用一两句话把思路讲给同桌听。能讲清楚才是真的学会了。