回文链表和相交链表是我给准备校招的同学做模拟面试时必考的两道题。题目本身难度不算高但能一次写出最优解的人真不多。原因很简单这两题表面是链表操作实际考的是两个通用模板——快慢指针和双指针接力。只要把模板吃透遇到环形链表、倒数第K个节点、链表求交点这些变体思路都能直接复用。这篇文章就把这两道题的原理、代码、易错点一次讲透适合刚刷完基础链表题、正在准备面试的读者也适合想系统整理链表模板的同学。1. 为什么链表面试总爱考回文和相交1.1 回文链表到底在考什么回文链表题目的表述非常简洁给你一个单链表头节点判断它是不是回文链表。所谓回文就是从头到尾读和从尾到头读得到同样的序列。比如1 - 2 - 3 - 2 - 1是回文1 - 2 - 2 - 1也是回文但1 - 2 - 3不是。看起来简单难点却藏在单向链表的结构里。单向链表只能从前往后走没法从后往前读。很多人第一反应是把所有节点值复制到数组或者栈里再倒序比较。这确实能通过但空间复杂度是 O(n)。在线评测系统通常不会拦住这种解面试官却会追问一句能不能做到 O(n) 时间、O(1) 空间这时候就真刀真枪地考基本功了。要判断回文必须同时拿到链表的前半段和后半段并且在空间受限的情况下只能原地操作。于是问题被拆成两个经典动作用快慢指针找中点再原地反转后半段。所以回文链表表面是判断题本质是“中点定位 链表反转 同步比较”的组合题非常考验边界控制。1.2 相交链表绕不开的坑相交链表的题干也不复杂给出两个单链表找出它们相交的起始节点没有交点就返回空。相交指的是两个指针最终指向同一个节点对象而不是两个节点的值相同。链表一旦相交从交点开始到末尾就是共享的一段节点两个链表形成一个 Y 字形状。这个题最容易踩的坑就是按值判断。两个值相同的节点完全可能各自独立根本不相交反过来真正相交的节点地址一定相同。所以正确的判断依据是节点地址不是节点内容。另一个常见解法是哈希表遍历链表 A把所有节点地址存进去再遍历 B 查表。这样能过但空间复杂度是 O(n)。最优解完全不需要额外容器只要让两个指针分别走完自己的链表然后交换到对方链表的头继续走总路程相等最终必然在交点相遇。这个思路后来被提炼成“双指针接力”模板解决的不只是这一道题。1.3 两个模板能覆盖多少场景快慢指针模板核心是一个指针每次走一步另一个指针每次走两步。利用速度差可以找链表中点、检测环、找倒数第 K 个节点。回文链表只是其中一个典型应用。双指针接力模板核心是让两个指针分别遍历两条链走完自己那条再走对方那条用总步长相同来消除两条链的长度差。相交链表是这个模板最自然的出处。很多同学刷题时喜欢一道题背一份代码遇到变体就懵。我更建议把这两套模板当成基础工具理解它们为什么能成立再把模板迁移到新题目里。下面就把两道题的原理和代码一层层剥开。2. 回文链表快慢指针加反转的最优解2.1 从暴力解到最优解的演进路线回文链表的暴力解法很好想遍历一次链表把节点值放进数组然后用双指针从两端往中间比较。空间 O(n)时间 O(n)。还有递归解法先递归到链表尾部回溯时再和头部比较逻辑上很优雅但递归调用栈同样占 O(n) 空间链表很长时还有爆栈风险。要压到 O(1) 空间思路就得变成把后半段链表原地反转让后半段变成从尾部到中点的方向然后与前半段逐点比较。比较完如果需要保持原链表结构就把后半段再反转回来。所以三个关键动作缺一不可找中点、反转后半段、同步比较。找中点用快慢指针反转用三指针迭代比较用两个指针从头和反转后的后半段同时走。整个过程只需要几个局部变量空间自然是 O(1)。2.2 快慢指针找中点的完整过程快慢指针找中点写法几乎固定ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; }循环结束的瞬间slow 指向的位置取决于链表长度。如果链表长度是奇数比如1 - 2 - 3 - 4 - 5slow 最终会落在正中间的 3 上。你可以手动模拟一下初始 slow 和 fast 都在 1第一轮 slow 到 2、fast 到 3第二轮 slow 到 3、fast 到 5第三轮发现 fast-next 为空循环停止。如果链表长度是偶数比如1 - 2 - 3 - 4初始都在 1第一轮 slow 到 2、fast 到 3第二轮 fast 到 4 后还有 next 吗4 的 next 是空但第二轮的判断发生在 fast 还指向 3 的时候3 的 next 是 4不为空于是进入循环slow 走到 3、fast 走到空。最终 slow 落在 3 上也就是第二个中间节点偏右的那一个。这个偏右的特性很重要。反转从 slow 开始的后半段奇数长度时会把中间节点一起算进后半段偶数长度时刚好是整个右半段。比较时中间节点和自己比较不会出现漏判或重判。2.3 原地反转链表的三个细节链表反转也是高频考点这里直接给迭代模板ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* nextNode cur-next; cur-next prev; prev cur; cur nextNode; } return prev; }有三个细节最容易出错。第一保存后继节点。cur-next prev会立刻让 cur 和原来的后继断开如果不先存nextNode后半段就丢了。这个保存动作要在修改 next 指向之前完成。第二返回的是 prev 而不是 cur。循环结束时 cur 已经为空prev 才是反转后链表的头节点。第三反转会修改原链表结构。如果题目要求不能改动链表比较完之后需要把后半段再反转回来把链表恢复原状。2.4 完整代码模板与链表恢复回文链表完整实现如下bool isPalindrome(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* secondHead reverseList(slow); // 反转后半段 ListNode* first head; ListNode* second secondHead; while (second) { if (first-val ! second-val) { return false; // 这里直接返回会留下被修改的链表 } first first-next; second second-next; } return true; }注意上面这个版本有个隐患一旦比较失败提前返回链表后半段已经被反转原链表结构被破坏。如果面试官要求不修改原链表需要改成先比较、后恢复的写法bool isPalindrome(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } ListNode* secondHead reverseList(slow); ListNode* first head; ListNode* second secondHead; bool result true; while (second) { if (first-val ! second-val) { result false; break; } first first-next; second second-next; } reverseList(secondHead); // 恢复后半段 return result; }恢复的原理是secondHead始终指向反转后的后半段头节点比较过程中 second 指针虽然移动了但 secondHead 不会变。对 secondHead 再执行一次反转后半段就回到原来的顺序。由于前半段和 slow 之间的连接从未被改动恢复后整个链表会还原成最初形状。实际面试中我在写代码前会主动问一句“链表可以修改吗”。大多数判题系统只看返回值不需要恢复但面试官问“能否不修改链表”时能立刻给出恢复方案印象分会差很多。3. 相交链表双指针接力的经典模板3.1 相交链表题意的完整拆解相交链表题目通常会给你两个链表的头节点要求返回交点没有交点就返回空指针。相交的定义是存在一个节点既属于链表 A也属于链表 B从这个节点开始后面的所有节点都共享。举例来说链表 A 是1 - 2 - 3 - 4 - 5链表 B 是9 - 3 - 4 - 5如果 3 是同一个节点对象那么交点就是 3。注意这里不能只看值链表 A 里的 3 和链表 B 里的 3 完全可以是两个不同的节点只有地址相同才算相交。还有一个隐藏前提这两个链表都没有环。经典的相交链表问题默认是无环单链表。有环的情况更复杂通常作为扩展题出现后面我会单独说。最优解法要求时间 O(n)、空间 O(1)而且不能修改链表结构。哈希表法虽然直观但空间不达标面试很容易被否掉。3.2 双指针接力为什么能消除长度差双指针接力的代码如下非常短ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }这段代码的精髓在于“换头”。pA 从 A 出发走完 A 之后不从 A 的末尾结束而是从 B 的头继续走pB 从 B 出发走完 B 之后从 A 的头继续走。为了说明为什么有效设链表 A 的长度为a c链表 B 的长度为b c其中 c 是公共部分的长度。如果没有交点可以理解为公共部分长度是 0两个链表在空指针处交汇。pA 走过的总路程是A 的非公共部分 a加上公共部分 c再从 B 的头开始走 B 的非公共部分 b总共a c b。pB 走过的总路程是B 的非公共部分 b加上公共部分 c再从 A 的头开始走 A 的非公共部分 a总共b c a。两个总路程完全一样所以两个指针会同时到达终点。有交点时这个终点就是交点没有交点时这个终点就是空指针。你可以把这个过程理解成两个跑步的人各自跑完自己的跑道后再交换跑道继续跑。两个人的总路程相同速度相同自然会在同一个时间点跑到同一个位置。代码里第二个关键点是用pA ? pA-next : headB做换头而不是用if (pA-next nullptr)判断。因为当 pA 已经到达链表 A 末尾时pA 本身不为空但 pA-next 为空。如果写成 pA-next 判断会让指针在最后一个节点停留一次逻辑就乱了。直接在当前指针为空时换头才是标准的“走完即换”。3.3 边界条件处理先看两个链表本身就是空的情况。headA nullptr且headB nullptr循环条件pA ! pB为假直接返回空正确。再看一个链表为空、另一个非空的情况。假设 headA 为空headB 是1 - 2。初始 pA 为空pB 指向 1进入循环后 pA 被赋值为 headBpB 往前走。最终 pA 走完整个 BpB 也到达空指针再循环后 pA 切到 headA 也为空两者都是空退出返回空。这个过程不会死循环因为两个指针走过的节点总数是有限的。再看交点在头部的情况。如果两个链表本身就共享从头开始的所有节点即 headA 和 headB 是同一个节点那么初始就有pA pB循环直接跳过返回该节点正确。关于无交点时会不会死循环不会。pA 最多走lenA lenB步pB 也最多走lenA lenB步两者同时走完同时变成空指针然后退出。整个过程是确定性的时间复杂度是 O(lenA lenB)。3.4 有环链表相交题的扩展思路经典解法默认无环但面试里可能被追问“如果链表有环怎么办”。遇到有环第一步是分别找两个链表的环入口。可以用快慢指针快指针每次两步慢指针每次一步相遇后把慢指针放回头节点两个指针都每次一步再次相遇的位置就是环入口。这个原理在环形链表相关题目里有详细推导这里不展开。找到环入口之后判断相交就要分情况。如果两个链表压根没有环回到经典解法。如果两个链表都有环先看它们的环入口是不是同一个节点如果是说明两者在环上相交如果不是还要判断其中一个链表的环入口能否绕到另一个链表的环入口。能绕到就说明它们在同一个环内相交否则不相交。有环情况在面试中属于加分项真正写代码时情况较多可以和面试官先对齐链表是否无环再决定要不要走这条深水区。4. 常见问题与排查技巧实录4.1 回文链表五个翻车现场我见过很多同学在纸上推演没问题一上机就错大部分集中在下面五个位置。第一个是快慢指针循环条件写错。有人写成while (fast-next fast-next-next)。这样在偶数长度时 slow 会落在偏左的中间节点即两个中间节点的前一个反转后半段时会把左侧中间节点一起拖进去比较逻辑立刻乱掉。我的习惯是统一用while (fast fast-next)配合偏右的 slow 落点。第二个是反转时丢链。典型错误是cur-next prev; prev cur; cur cur-next; // 错cur-next 已经被改了修改 cur-next 之前没有保存后继后面的节点全部丢失。正确做法是用临时变量先存 nextNode。第三个是比较循环的控制条件写错。有的写while (first ! slow)有的写while (first),都会导致奇数偶数时比较次数不一致。正确做法是以反转后的后半段指针为基准即while (second)因为后半段的长度一定不超过前半段加中间节点second 走完时比较也刚好结束。第四个是恢复链表失败。提前 return 很容易忘掉恢复动作。建议不要过早 return把结果存到一个 bool 变量里跳出循环后再统一恢复链表最后 return。第五个是空链表和单节点链表没处理。大量在线判题系统会把空链表当作回文处理返回 true。单节点链表也是回文。代码里reverseList(nullptr)会返回空while (second)直接不执行返回 true所以只要不在边界写死if (head nullptr) return false默认逻辑就是对的。4.2 相交链表四个隐蔽坑点相交链表代码虽然短坑却不少。坑一把值相等当成相交。这是最致命的理解偏差。两个链表里出现相同值的节点再常见不过但是它们的地址互不相同根本不共享。判断相交的唯一标准是指针相等也就是节点地址相等。坑二空链表情况处理不当。如果某个链表是空直接返回空即可。双指针模板天然支持但如果在循环里写while (pA-next || pB-next)空链表会立刻触发空指针访问。坑三循环内忘记更新指针导致死循环。有些初学者写while (pA ! pB)循环体里看起来有赋值但条件不满足时某个指针一直没变化。排除方法是手动模拟两个链表打印 pA 和 pB 每次的位置或者直接在纸上把移动轨迹画出来三步之内就能发现问题。坑四无交点但期望返回空。双指针模板在无交点时会让两个指针同时走到空返回空指针代码是对的。但有人会在循环结束后写return nullptr这也没问题只是要确保不是提前 return。如果你在调试相交链表时发现结果不稳定优先检查链表初始化时是否人为制造了每个节点的 next 指向而不是让两个链表真正共享同一段内存。测试用例如果只是“碰巧值一样”代码再怎么写也找不到交点。4.3 面试追问应对与复杂度表述面试官问到复杂度回文链表要回答“时间 O(n)空间 O(1)”。注意这里指的是最优解法如果额外做了链表恢复恢复过程也是 O(n) 时间和 O(1) 空间总复杂度不变。问到能否不修改链表可以回答判断过程需要临时反转后半段比较之后把后半段再反转回去原链表会恢复到初始状态。这不算永久修改但如果严格要求过程中也完全不改变结构只能用栈或递归空间会变成 O(n)。面试场景下最合理的表述是“我能做到 O(1) 空间并且会在返回前恢复链表”。问到相交链表为什么正确把 3.2 节的总路程公式讲清楚就行。用“两条链表总长度相同”来解释比干巴巴背代码更容易让人信服。问到能不能用哈希表解相交链表承认“思路可行、空间不优”就好。面试官真正想听的是你能不能自己提出并推导出双指针接力方案。5. 刷题建议与两个模板的复用心得5.1 从背模板到灵活迁移我建议把模板拆成最小单元来练而不是整道题一起背。快慢指针模板的最小单元是“找链表中间节点”反转链表模板的最小单元是“三指针反转”双指针接力模板的最小单元是“两条链总长度相同则同步相遇”。把这三个最小单元练熟后回文链表和相交链表就是拼装题。再往远看找链表倒数第 K 个节点可以用快慢指针先让快指针走 K 步判断链表是否有环可以用快慢指针看是否相遇找环形链表环入口还要再结合一次重新出发。双指针接力模板还能用在判断两个链表是否相交的变体题里。有的题目会要求你只返回 true 或 false不要求返回节点双指针接力一样成立因为如果有交点两个指针必然相遇没有交点则同时到达空。这类变体在面试里出现频率不低。5.2 推荐刷题顺序如果你想用这两个题来练兵我建议按下面的顺序走先刷链表反转确保闭着眼睛能写出三指针迭代再刷找链表中间节点用快慢指针跑一遍奇数长度和偶数长度的用例然后刷回文链表把反转和找中点合在一起接着刷环形链表理解快慢指针判环最后刷相交链表熟悉双指针接力。这样拆开练每一步的难点都被单独击破最后拼装时不会觉得难度突增。很多同学直接上来硬刷回文链表反转和找中点都生疏一个题卡两小时反而打击信心。5.3 最后说点实操中的大实话我在模拟面试里看过太多次“草稿纸上对了编辑器里跑崩”的情况。链表题最实用的自查方法是在写代码之前先在草稿纸上列三个用例空链表、单节点链表、正常回文/非回文链表。这三个用例能覆盖大部分边界问题。还有一个习惯很推荐写完代码先别着急提交手动走一遍偶数长度回文链表的流程。因为偶数长度最容易暴露快慢指针落点选错的问题走完这一步基本就能确认代码有没有考虑完整。回文链表和相交链表之所以值得反复练不是因为它们难而是因为它们把链表题里最高频的两种思想浓缩在了一起。快慢指针解决“位置问题”双指针接力解决“长度差问题”。把这两套模板真正吃透面试手写链表题时你会明显感觉底气不一样。