如果让我给链表面试题列一份“必刷清单”回文链表和相交链表一定排在前三名。前者把快慢指针、链表反转、双指针比对三件事缝在一起后者则用最简洁的双指针相遇法证明了链表面试题也可以有数学美感。这两道题的最优解法都不难但我在模拟面试中见过太多人“思路秒懂一写就错”——不是反转时丢了 next 引用就是快慢指针的边界条件写错再或者相交链表的指针换道写成死循环。这篇文章不打算罗列所有解法只围绕最优解法展开把两套模板拆开揉碎让你能直接背进脑子里、用在面试的白板上。如果你刚开始刷链表可以先收藏慢慢看如果你已经刷了几轮重点看后面的边界与记忆法。下面按“为什么考、怎么做、怎么写、怎么避坑”的顺序走两道题都会给出可直接复用的代码模板。1. 面试官出这两道题到底在考察哪三样能力刷链表题的人通常会经历三个阶段第一阶段是照着遍历模板死记第二阶段是能做出中等题第三阶段是看到题目就能在脑中拆解成“若干基础操作的组合”。回文链表和相交链表正好能把人从第二阶段推到第三阶段因为它们的解法不是穿上一件新奇的外衣而是把几个最基础的动作拼装起来。为什么这两道题高频我认为有三点。第一单链表这种结构的本质是“只能顺着 next 走不能回头也不知道长度”。凡是需要回头访问的诉求都要借助额外手段这就天然制造了考点。第二链表题的安全感来自对空指针的敏感度也就是 next 为 None 时的处理回文链表和相交链表恰恰在最容易被忽视的边界处设伏。第三这两道题的标准解法足够简练考察的是“会用工具而不是堆工具”。拆开来看回文链表表面上是一个“判断是否对称”的题目实际上抽掉对称这个外衣后考点是三个能否把数组双指针的技巧平移到链表上能否找到链表中点能否把后半段反转回来。这三个动作里任意一个都不难但缝合在一起时很多人会把顺序搞反。比如有的人先反转整条链表再比较两个链表这样虽然也能判断回文但需要额外复制一份链表空间就变成 O(n) 了不是最优。相交链表则更微妙。它不需要反转也不需要找中点核心只有一件事两条链的起点不同终点处的交汇段相同如何让两个指针在“相同长度”的路径上相遇。听上去有点绕但一旦接受“走完自己的路就去对方的路上走”这种设定代码只有几行。还有一点值得单独拿出来说就是最优解法的评判标准。面试中的“最优”不是单纯的时间复杂度最低而是时间和空间两个维度上的综合平衡。这两个题的标准最优解都是 O(n) 时间、O(1) 空间而且不依赖破坏链表本身结构或者比较结束后能恢复原状。如果哪个解法用了哈希集合或者数组哪怕时间达标也会被追问一句“空间能不能降到常数级”提前想清楚这层面试状态会好很多。2. 回文链表快慢指针定位中点反转后半段再比较先明确题目给定一个单链表的头节点 head判断它是不是回文链表。所谓回文就是从前往后读和从后往前读得到的序列一致。比如 1-2-2-1 是回文1-2-3 不是。这道题网上能看到很多写法但真正值得掌握的最优解只有一条主线快慢指针找到前半段的尾节点然后反转后半段最后用两个指针从头部和后半段头部同步往中间走逐个比较节点值。下面拆开讲每一步。2.1 先聊为什么不能只停留在“转数组”解法大多数人看到回文的第一反应是把链表遍历一遍值存进数组然后用数组双指针从两端往中间走。这个解法完全正确代码也很短def is_palindrome(head): vals [] while head: vals.append(head.val) head head.next left, right 0, len(vals) - 1 while left right: if vals[left] ! vals[right]: return False left 1 right - 1 return True时间复杂度是 O(n)没问题但空间复杂度是 O(n)。刷题平台或者面试官通常会要求“进阶做法”也就是 O(n) 时间、O(1) 空间。这个进阶要求直接把数组法否决了。还有一种常见思路是“反转整个链表再和原链表比较”但这样做必须先完整复制一份原链表否则原链表被反转破坏后就没法比对了。复制一份的代价同样是 O(n) 空间而且多了一次完整遍历代码更啰嗦。递归也能做先用递归走到链表尾部然后从尾部开始和头部依次比较。这个思路类似“后序遍历”逻辑上很优雅但递归栈的深度是 O(n)同样不满足常数空间的进阶要求而且在链表特别长的时候有栈溢出的风险。所以最优解只能是不借助外部容器就在链表内部用指针操作完成。2.2 快慢指针找中点长度奇偶时的落位差异要在一个单链表里找中点不能用下标只能用“快慢指针”。这个技巧可以类比两个人同向跑步跑得快的人速度是慢的人的两倍当快的人到达终点时慢的人正好在全程的一半位置。代码写法有很多种最容易记混的是 while 条件。我推荐固定使用下面这种slow fast head while fast.next and fast.next.next: slow slow.next fast fast.next.next为什么这里的循环条件要写成fast.next and fast.next.next而不是常见的fast and fast.next因为两者在“奇偶长度时 slow 停的位置”上完全不同。看一个奇数长度的例子链表 1-2-3-2-1长度 5。初始 slow 在 1fast 在 1。第一轮循环slow 到 2fast 到 3。第二轮循环slow 到 3fast 到 5末尾节点。此时fast.next为 None循环退出。最终 slow 停在值 3 的节点也就是前半段 1-2-3 的最后一个节点。注意这里把正中间的节点 3 归进了“前半段”这是奇数长度下很自然的处理方式因为中间节点不需要参与比对。再看一个偶数长度的例子链表 1-2-2-1长度 4。初始 slow 在第一个 1fast 在第一个 1。第一轮循环slow 到 2fast 到第二个 2。第二轮判断时fast.next为 None循环退出。最终 slow 停在第一个 2也就是前半段 1-2 的最后一个节点后半段从 slow.next 开始正好是 2-1。前后两段长度完全相等非常对称。如果用while fast and fast.next这种条件偶数长度时 slow 会停在“中间偏右”的位置奇数长度时停在正中间这两种情况下后半段的起点都会偏向一侧比较时容易多走或者漏走一个节点。所以别贪图和省事固定用fast.next and fast.next.next配合“slow 最后是前半段尾节点”这个认知写起来最稳。2.3 反转后半段与逐项比对的完整代码模板找到前半段尾节点之后后半段起点就是 slow.next。接下来要把这段反转过来反转链表的模板必须烂熟于心。我在这里把回文链表判断的完整模板给出来也包含了反转链表的辅助函数class Solution: def is_palindrome(self, head: ListNode) - bool: if head is None or head.next is None: return True # 1. 快慢指针找到前半段的尾节点 slow fast head while fast.next and fast.next.next: slow slow.next fast fast.next.next # 2. 反转后半段 second_head self._reverse(slow.next) # 3. 从头部和后半段头部同时出发逐个比对 p1, p2 head, second_head result True while p2: if p1.val ! p2.val: result False break p1 p1.next p2 p2.next # 4. 恢复链表原状 slow.next self._reverse(second_head) return result def _reverse(self, head: ListNode) - ListNode: prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev注意第三步的循环条件是while p2也就是以后半段为主循环。因为后半段的长度最多等于前半段所以只要 p2 还没走完就需要继续比较如果前半段比后半段多出来的节点只可能是奇数长度时的正中间节点那个节点本来就无所谓和谁比。第四步叫“恢复链表”这一步在一些判题场景里不是必须的但在工程习惯和面试追问里非常加分。原因很简单你反转了后半段等于修改了原始链表结构。如果调用方后面还要遍历这个链表或者测试框架会检查链表是否被改动不恢复就会出问题。恢复的方式就是把后半段再反一次然后用 slow.next 接回去代码和之前反转用的是同一个辅助函数。2.4 恢复链表面试官好感度加分项很多参考答案都不会提“恢复链表”这一步因为它不影响最终返回结果。但我在实际面试模拟中观察到一个现象候选人只写出四步里的前三步时面试官通常不说什么一旦候选人自己补了一句“最后我可以把链表恢复原状”面试官会明显点头。原因是恢复链表体现的是工程意识而不是“刷题机意识”。线上系统的判题通常只看返回值不在乎链表在函数返回后长什么样但真实代码库里一个函数不应留下副作用。所以我的建议是面试时主动说“这里比较完成后我会把后半段再反转回去让链表保持原样”然后把第四步写上。多一行调用辅助函数的代码就能多一个亮点。你可能担心恢复链表会破坏 result 变量或者影响返回结果其实不会。result 在关闭比较循环后已经确定后面的恢复操作只是改变链表结构不再改变返回值。这一点写代码时可以放心。3. 相交链表换道双指针相遇数学上为什么一定是对的相交链表的题目描述是给定两个单链表的头节点 headA 和 headB在链表中找出两个链表相交的起始节点如果两个链表没有交点返回 null。这里的“相交”必须理解清楚不是两个节点值相等而是两个指针指向的节点在内存中是同一个对象换句话说从某个节点开始两条链表共用同一段节点序列。正因为指向同一个对象所以可以用“指针相等”来判断。这也是很多第一次做的人踩的坑看到值相等就返回结果错得一塌糊涂。为什么说这道题是一道数学味很浓的链表题因为它最优解法的正确性证明靠的只是一个简单的等式。3.1 长度差法最稳妥的直观解法在讲双指针相遇法之前先讲一个更直观的模板长度差法。思路是两条链表相交的话从交点开始往后的长度是完全相同的所以交点之前的长度差是固定的。具体步骤有三步分别遍历 headA 和 headB得到两条链表的长度 lenA 和 lenB。让较长的那个链表指针先走 |lenA - lenB| 步把长度差抹平。两个指针再同步往前走每走一步都比对一次节点引用直到同时到达同一个节点或者同时走到 None。如果相交第一个相同节点就是交点如果不相交两个指针最终会同时走到链表末尾的 None。时间复杂度是 O(lenA lenB)因为最多遍历两遍链表空间复杂度是 O(1)。def get_intersection_node(headA: ListNode, headB: ListNode) - ListNode: lenA, lenB 0, 0 pA, pB headA, headB while pA: lenA 1 pA pA.next while pB: lenB 1 pB pB.next pA, pB headA, headB if lenA lenB: for _ in range(lenA - lenB): pA pA.next else: for _ in range(lenB - lenA): pB pB.next while pA ! pB: pA pA.next pB pB.next return pA这个写法最大的优点是好解释、好证明。面试时如果怕自己紧张失智长度差法是最保底的选择。它虽然比双指针相遇法多了一段计算长度的代码但每一步的逻辑都非常直白不太可能写错。3.2 双指针循环法从“换一条路走”到“必然相遇”双指针相遇法的代码更短而且极端巧妙。它的思路是两个指针分别从 headA 和 headB 出发各自走完自己的链表之后跳到对方的链表继续走。由于两个指针走过的总路程可以设计成相等它们必然在交点相遇如果没有交点它们最终会同时到达链表末尾的 None循环自然退出。直接上代码def get_intersection_node(headA: ListNode, headB: ListNode) - ListNode: if headA is None or headB is None: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA只有几行但正确性需要一点数学推导。假设链表 A 在交点前的独有段长度为 a链表 B 在交点前的独有段长度为 b两条链表从交点开始共用的段长度为 c。那么pA 从 headA 出发先走完 A 的整条链a c 步到达 A 的末尾 None。然后跳到 headB再走 B 的独有段 b 步到达交点。它一共走了 a c b 步。pB 从 headB 出发先走完 B 的整条链b c 步到达 B 的末尾 None。然后跳到 headA再走 A 的独有段 a 步到达同一个交点。它一共走了 b c a 步。因为 a c b b c a所以两个指针必然在同一个时刻、同一个节点相遇。这就是“换道双指针”的数学基础。如果两条链表不相交呢此时可以把公共段长度 c 看作 0。pA 走 a b 步到达 NonepB 走 b a 步到达 None两个指针同样会在同一时刻到达同一个位置也就是 None。这说明代码里的while pA ! pB循环会正常结束然后返回 pA也就是 None。不存在死循环的问题。我再用一个具体数字演示一遍。假设 a3b4c2。pA 走过的节点位置序列是A 的 3 个独有节点、公共段 2 个节点、跳到 B 后走 4 个独有节点、再到公共段。pB 走过的节点位置序列是B 的 4 个独有节点、公共段 2 个节点、跳到 A 后走 3 个独有节点、再到公共段。两个序列都在各自长度 9 的位置落到同一个交点。千真万确。3.3 两种模板怎么选以及三个必须处理的边界到了面试现场你不需要纠结“哪种更高端”我的建议是思路阐述用长度差法代码输出用双指针循环法。长度差法的逻辑最容易让面试官听得懂双指针循环法的代码最简洁、最显功力。如果你只来得及记一种我建议记双指针循环法因为它短短就代表着写错的概率低。不过双指针循环法有几个边界必须小心处理。第一任一链表为空直接返回 None。如果 headA 或 headB 是 None两个指针不可能有交点。代码里第一行判断就是这个用途。第二两条链表可能从头节点就是同一个。这种情况出现了headA headB双指针循环法在进入 while 之前就满足 pA pB直接返回 headA结果正确不需要额外处理。第三两条链表不相交。代码最终会让 pA 和 pB 同时变成 None然后 while 条件不成立返回 None。关键在于指针换道时的写法换道的依据是“当前指针是否为空”而不是“当前指针的下一个是否为空”。pA pA.next if pA else headB这里用的是if pA不是if pA.next。如果写成if pA.next当 pA 走到链表末尾时pA.next 是 None取反后跳到 headB看起来也能运行但逻辑上你是用“下一跳为空”来触发换道这会导致最后一轮比较的时机错乱甚至会反复在两条链的空节点之间打转变成死循环。这种错误非常隐蔽因为不是每次运行都必现只有空链表或者恰好长度差为 0 时会触发。3.4 代码模板两套写法都收好为了方便直接背诵我把两个模板放在一起。面试点名“相交链表”时你可以在心里先放着长度差法再写出双指针循环法。长度差法def get_intersection_node(headA: ListNode, headB: ListNode) - ListNode: pA, pB headA, headB lenA lenB 0 while pA: lenA 1 pA pA.next while pB: lenB 1 pB pB.next pA, pB headA, headB diff abs(lenA - lenB) if lenA lenB: for _ in range(diff): pA pA.next else: for _ in range(diff): pB pB.next while pA ! pB: pA pA.next pB pB.next return pA双指针循环法def get_intersection_node(headA: ListNode, headB: ListNode) - ListNode: if headA is None or headB is None: return None pA, pB headA, headB while pA ! pB: pA pA.next if pA else headB pB pB.next if pB else headA return pA两道题到这里核心解法已经全部给出。接下来要解决的是“怎么记得住”和“现场怎么输出”的问题。4. 两套模板的联动记忆法与面试现场输出节奏很多人刷题有一个痛点当时看懂了隔两天再写又卡壳。链表题的解法尤其如此因为代码不长但每个步骤之间的顺序和边界条件非常多稍不留神就会变成“感觉会了写完总差一点”。我的经验是把模板压缩成几句本金句配合现场输出顺序能大幅提高稳定性。4.1 快慢指针与反转链表的“口诀化记忆”回文链表这道题可以记成一个四拍口诀快慢找中反转后半双针比对顺手复原。“快慢找中”对应的是while fast.next and fast.next.next这个循环条件。为什么慢指针最后一定停在“前半段的尾节点”因为快指针每轮跳两步慢指针每轮走一步当快指针不能再往前跳两步时慢指针刚好完成了“走到一半”的任务。记忆时不要背代码背这句话就行了。“反转后半”对应辅助函数_reverse。反转链表的四个动作也要口诀化先存后指再动前三动后。展开讲就是先保存当前节点的下一个节点 nxt再把当前节点的 next 指向 prev接着把 prev 移动到当前节点最后把当前节点移动到 nxt。这四个动作缺一不可尤其是第一步“先存”很多人就是因为没存直接断链翻车。4.2 相交链表双指针的“路径公式记忆”相交链表这道题的记忆点只有一条路径公式a c b b c a。这个等式就是双指针循环法的灵魂。代码层面的记忆也可以压缩成三句话两个指针同时出发谁走到头就换到另一条链的头部继续走到两个指针相等为止。注意“走到头”的意思是当前指针变成 None而不是“再走一步就变 None”。代码里我刻意写成pA.next if pA else headB核心就是“看当前位置而不是看下一个位置”。你甚至可以这样记链表世界里的“换道”永远发生在你真正撞到 null 之后而不是站在最后一个节点上提前变道。这两道题放在一起记还有一个隐藏彩蛋它们共用同一套基础能力。回文链表用到“快慢指针 反转链表 双指针比对”相交链表用到“双指针变道 边界判空”。一旦把这些子操作练成肌肉记忆以后遇到“判断链表是否有环”“寻找环形链表入口”“删除倒数第 N 个节点”等题目都能直接迁移过去。4.3 白板面试的书写顺序先一句话定解法面试现场最怕的不是不会做而是开场即写写完发现思路有误只能擦掉重来。我的建议永远是一句话定解法然后再动笔。以回文链表为例你可以这样对面试官说“我先把链表分成前半段和后半段反转后半段之后两个头指针同步比过去时间 O(n)、空间 O(1)。”这句话说完你已经在为自己的代码划定边界了。以相交链表为例你可以说“两个指针从两条链的头出发走到尾部就跳到另一条链的头部因为它们总路程相同有交点就会相遇没有交点就同时到空。”这既是给面试官听的也是给自己梳理逻辑的。动笔顺序也有讲究。我的习惯是先写辅助函数比如反转链表再写主函数。这样主函数调用的结构一目了然。写完主函数的骨架之后我还会顺手在关键位置补注释比如“找前半段尾节点”“反转后半段”方便面试官跟着你的思路走。最后务必在代码写完后主动说一行复杂度回文链表是 O(n) 时间、O(1) 空间相交链表双指针循环法同样是 O(n) 时间、O(1) 空间。很多候选人忽略这个最后一步但面试官通常会听所以不要等对方问自己先说。5. 我自己踩过的边界坑条件写错、断链、死循环下面这部分是我在不同场合里反复见到的真实翻车现场。它们单拎出来都是小问题但在面试高压下任何一个小问题都可能导致整道题重写。我尽量把完整场景和排查过程还原出来这样你踩到类似的坑时能瞬间想起来。5.1 快慢指针条件写错奇数长度判断全部翻车我见过一位同学在写回文链表时快慢指针的循环条件写成了while fast and fast.next:。当时他用的测试数据是奇数长度的回文链表比如 1-2-3-2-1。跑的时候一切正常正好也能输出 True。我建议他换一个奇数长度的非回文链表试试结果输出了错误答案。排查过程是这样的我们打印了每一轮循环里 slow 和 fast 的位置。在长度 5 的链表里使用while fast and fast.nextfast 会在第三轮时从末尾节点走到 next也就是 None然后条件不满足退出。这时候 slow 停在了值 2 的节点也就是正中间节点的右边一位。后面反转 slow.next 时起点并不是后半段的开始位置而是已经偏移了一个位置导致比较出现了“错位”。这个问题最麻烦的地方在于如果测试数据恰好比较凑巧错位也可能歪打正着输出正确结果最典型的是长度为 3 的简单回文链。一旦备用组数据长度稍长就露馅。这个案例给我的教训是快慢指针的 while 条件必须和“slow 最终落在哪个位置”绑定记忆不能每次临场推演。5.2 反转链表时丢失 next 引用反转链表是链表题里最基础的操作但也是出错率极高的操作。典型错误代码长这样curr.next prev prev curr curr curr.next看起来逻辑完整实际上第三行访问的 curr.next 已经不是原来那个 next 了因为第二行你刚刚把 curr.next 改成了 prev。也就是说连续节点之间的引用在你操作第一步时就被切断后面的节点全部找不回来。我刚开始练链表题时也翻过这个车。当时的现象是反转链表之后总感觉少了几个节点链表结构变得残缺。后来我把代码拆成四步每一步都用变量名约束住nxt curr.next先把下一个节点抓住。curr.next prev再掉转当前指针。prev curr把前驱指针移动到当前节点。curr nxt最后才移动到原先的下一个节点。这个顺序不能换尤其是第一步必须最早做。你可以把它想象成“先拉住手刹再换挡”顺序反了车就滑走了。5.3 相交链表指针换道时没判空导致死循环相交链表的双指针循环法短但短代码里藏着一个极其隐蔽的空指针问题。错误版本是这样while pA ! pB: pA pA.next if pA.next else headB pB pB.next if pB.next else headA乍一看好像更“安全”因为判断的是 pA.next 而不是 pA 本身。但问题是当 pA 走到链表的最后一个节点时pA.next 为 None于是触发换道跳到 headB。这看起来没问题但换道的时机已经晚了半拍——你本来应该在“走到终点”也就是 pA 为 None 的时候换道而不是在最后一个有效节点上提前换。举个例子两条链表长度相同且不相交。pA 和 pB 会同时从各自的头部出发一步一步往前走。到达各自链表的最后一个节点后pA.next和pB.next都是 None于是同时跳到对方的头部。接下来它们又同时从头走到末尾时又同时跳回原来的链。整个过程会无限循环因为 pA 和 pB 永远在两条链的节点之间交替移动但永远不会同时为 None也就永远不会有相等的时候。正确写法一定是基于当前指针是否为 None 来判断换道。这不仅仅是语法问题而是是否理解了双指针循环法真正的终止条件。写代码时只要坚持“先判自身是否为空再换道”这类死循环就与你无缘了。5.4 建议随身跑的边界用例清单最后给出一份我平时练手必跑的用例清单。刷题平台不一定帮你想全但面试现场的人工追问往往会覆盖这些角落。场景用例预期结果空链表head None回文返回 True相交返回 None单节点[1]回文返回 True双节点回文1-2-2-1返回 True双节点非回文1-2返回 False奇数长度回文1-2-3-2-1返回 True奇数长度非回文1-2-3-4-1返回 False偶数长度回文1-2-2-1返回 True相交但前段长度不同A: 1-2-3-XB: 9-8-7-6-X返回 X 节点相交且起点相同headA headB返回 headA不相交但长度相同A: 1-2B: 3-4返回 None不相交且长度不同A: 1-2-3B: 4返回 None把这些用例跑一遍两个模板的边界基本就夯实了。你甚至可以写成一个小脚本每写完一次模板就自动跑一遍全部通过后再停笔。最后再分享一个小技巧。别只在脑子里过代码我强烈建议你把上面这些边界用例做成一个可以反复运行的小测试脚本每次写完模板就跑一遍确认没有死循环、没有断链、没有错位。当你能在五分钟内把两个模板加这些用例完整跑通你会明显感觉到面试的时候心里有底得多。链表面试题变来变去很多本质上都是“定位节点、反转一段、双指针比对”的组合把这两道题的模板吃透比闷头刷几十道题更划算。