单链表回文判断这个问题我在面试实战里遇到的次数不少工作后也常拿它来给组里的新人练手。它不像红黑树、图算法那么唬人但恰恰是这种“看起来简单、写起来全是坑”的问题最能看出你对链表指针操作是否真的熟练。判断一个单链表是否回文通俗地说就是链表从头往后读和从尾往前读得到的结果一样比如1-2-3-2-1就是回文结构。能解决什么问题呢像某些字符串对称校验、链表版本的数据存储都需要类似的比较逻辑。这篇文章适合正在准备算法面试的同学也适合想系统补一补链表基本功的开发者。我会从最底层的节点定义讲起把找中点、链表逆序、回文比较这几件事拆开揉碎最后给出一份可以直接跑起来的完整代码。我现在还清楚地记得自己第一次写这道题时的狼狈快慢指针的边界条件搞不清逆序到一半指针丢了最后比较时又发现原链表已经被改得面目全非。这些都是新手必踩的坑。本篇文章的目标就是帮你把这些坑一个不落地都填上。1. 回文判断这个经典问题为什么值得再写一遍1.1 单链表回文是什么先对齐概念回文Palindrome这个词原本用在字符串上正着读和倒着读都一样比如“level”“radar”。放到单链表场景里概念完全同理链表从头到尾依次取值和从尾到头依次取值得到完全相同的序列。比如下面这几个链表1-2-3-2-1回文1-2-2-1回文1-2-3-4不是回文a-b-a回文空链表和只有一个节点的链表按惯例都算回文这个定义本身不难难在单链表的数据结构特性上。数组存值想从后面往前扫描直接按下标减一就行而链表节点只有next指针没有prev指针想访问前一个节点要么重新从头遍历要么额外记录要么就把链表局部倒过来。理解了这个本质差异后面所有方案的取舍逻辑就都顺理成章了。1.2 数组判断和链表判断的本质差异假设你手里是普通数组判断回文最直白的做法是双指针左指针从头开始右指针从末尾开始两边的值逐对比较一直移动到中间汇合。整个过程的时间复杂度是O(n)额外空间是O(1)代码简单到三分钟就能写出来。为什么到了链表就变得麻烦因为“右指针从末尾开始”这一步做不到——链表是单向的你拿不到“末尾的前驱”除非你遍历一遍先记下来或者设计出一个能从尾往头走的遍历方式。所以链表判断回文的核心矛盾是如何在一个只能向前走的线性结构中模拟出从两端往中间比较的效果。抓住了这个矛盾你再看各种实现方案——辅助栈、后半段反转、递归回溯——就会发现它们本质上都在回答同一个问题怎么让“尾部元素”先于“前驱元素”被访问到。这样一梳理算法就不再是一堆零散技巧的堆砌了而是同一个问题下的不同策略选择。2. 四条主流实现路线各自踩准哪个点2.1 反转后半段空间O(1)的经典思路被面试官问到链表回文时我最推荐的第一反应就是“反转后半段”这个方案。它分为四步用快慢指针找出链表的中间位置将中间位置之后的半段链表原地反转从头部和反转后的半段头部同时开始逐一比较节点值如果想保持原链表结构不变再把后半段反转回来。这个方案的亮点是额外空间复杂度可以压到O(1)因为链表的逆序操作是在原节点的指针域上完成的不借助额外数组或栈。缺点是它改变了链表结构虽然可以恢复并且步骤较多、容易在中点定位和逆序阶段出错。工程面试中这个方案既能考察你对快慢指针的理解又能考察指针操作基本功出镜率极高。为什么选择反转后半段而不是反转整个链表这是一个很关键的想法。如果反转整个链表链表变成了从尾部向前的结构你确实可以拿到一个“从原来末尾开始的表头”但你同时也失去了原链表的表头。要从两边同时比较就需要同时持有原链表头部和逆序后的头部而反转整条链表后原头部被“甩”到了链表尾部根本没有办法在保持后续连接的同时作为左端点继续前移。反转半段则不然前半段保持原样后半段逆序左右两边各有明确的起点比较过程干净利落。2.2 借助栈与快慢指针空间换时间的朴素方案如果不允许修改链表又不想依赖递归辅助栈是最直观的方案。这里有两种玩法。第一种是暴力全栈法遍历整个链表把每个节点的值压入栈。因为栈是后进先出的所以当遍历结束后从栈顶开始弹出的顺序恰好就是链表的逆序。此时再从头遍历一次链表每到一个节点就弹出一个栈顶值做比较。如果中途出现不相等返回False如果整个链表遍历完都没问题返回True。这个方案时间O(n)空间O(n)。代码非常容易写几乎不会犯错代价就是多一份内存开销。第二种是半程栈法先让快指针一次走两步、慢指针一次走一步当快指针走到链表末尾时慢指针刚好停在中间。接着让慢指针继续走完剩下的半段并把沿途节点值依次压栈。此时栈中的值正好是链表后半段的逆序。然后把慢指针重置回链表头部开始和栈顶逐一比较。这里只压入半段节点空间占用比全栈法少一半但依然需要O(n/2)的空间属于典型的O(n)额外空间换代码可读性。有个细节值得注意用栈方案比较时比较长度只需要取后半段长度没必要再遍历整个链表。因为前半段和后半段长度相等偶数长度或后半段比前半段少一个节点奇数长度无论哪种比较次数都等于后半段长度。如果左右值全部相等前面那些多出来的中间元素奇数长度时不影响回文结论。2.3 递归与数组辅助适合教学但不适合工程递归方案的思路也很精妙让函数一层层往里递归调用直到最后一个节点才停下然后在“归”的过程中借助一个外部的“左指针”和当前节点依次比较。这利用了函数调用栈天然后进先出的特性等于替我们实现了一个隐式的栈。举个例子left head def helper(node): global left if not node: return True if not helper(node.next): return False if left.val ! node.val: return False left left.next return True看起来简洁实际存在两个问题第一递归深度等于链表长度链表一长就会栈溢出第二这个方案难以在多线程或不允许多次递归的环境里使用。所以我通常建议读者把它当成理解“递归回溯顺序”的练习题而不是工程首选。数组辅助方案就没什么神秘的了遍历链表把值全部采集到列表里然后用数组的双指针法做回文判断。它的空间O(n)时间O(n)逻辑极其清晰。好处是不修改原始结构代码不容易出错代价则是额外的内存占用。在刷题场景里如果能问清楚面试官“是否允许使用额外O(n)空间”数组法是最稳妥的兜底方案尤其适合短时间内需要快速产出解法的情况。2.4 路线对比与选型建议我整理了一张对比表把这几种方案的特性放在一起看方案时间复杂度额外空间复杂度是否修改原链表代码复杂度适用场景反转后半段O(n)O(1)是可恢复较高面试主推、空间敏感场景辅助栈全栈O(n)O(n)否低快速实现、教学演示辅助栈半程O(n)O(n/2)否中对空间有一点要求但不苛刻递归回溯O(n)O(n)系统栈否低教学演示、短链表数组双指针O(n)O(n)否低最简单兜底方案我个人在实际项目里的选择习惯是如果只是做一次性判断链表规模不大用数组辅助法最省心如果是作为面试手写题重点展示反转后半段这套组合拳因为它能在O(1)空间里解决问题考察点也更集中如果在生产代码中需要反复进行回文判断且链表对象不允许被破坏我会考虑空间换时间直接维护一个双向结构或者缓存值列表。技术选型没有绝对好坏唯一的准则是先弄清楚约束条件——能不能改结构、有没有空间限制、链表可能多长、是否需要频繁判断。把这些问清楚方案就自己浮出水面了。3. 核心实现快慢指针找中点、就地逆序、双指针回文校验3.1 关键操作一快慢指针与中点定位快慢指针是整个方案的第一步也是边界问题最多的一步。写错了后面全盘皆错。它的大体逻辑是让慢指针每次走一个节点快指针每次走两个节点同步出发。当快指针到达链表末尾或者无法再走下一步时慢指针就会停在链表的中部。为什么快指针走两步、慢指针走一步就能相遇在中点这其实就是速度差问题。假设链表长度为n快指针速度是慢指针的两倍经过t步后快指针走过了2t个节点慢指针走过了t个节点。当快指针到达尽头2t约等于n时t约等于n/2也就是慢指针走了一半路程。这个朴素的追及模型就是快慢指针找中点原理的全部秘密。代码实现时需要区分两种长度情况def find_middle(head): if not head: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow如果链表长度为奇数比如1-2-3-2-1慢指针最终停在正中间的节点3如果链表长度为偶数比如1-2-2-1慢指针最终会指向右半段的第一个节点也就是第二个2。这个行为不是偶然而是循环条件while fast and fast.next决定的。理解这一点特别重要因为后续要从慢指针这个位置开始反转后半段如果起点选错比较时就会出现错位。3.2 关键操作二单链表逆序的正确姿势反转单链表是另一个高频考点也是回文方案里的“重武器”。在回文场景里我们只需要反转从slow到末尾的这段链表但逆序的核心逻辑跟反转整条链表完全一样。经典迭代逆序法用三个指针def reverse_list(head): prev None cur head while cur: next_node cur.next # 先保存下一个节点否则指针会断 cur.next prev # 把当前节点的next指向前一个节点 prev cur # prev后移 cur next_node # cur后移 return prev # 逆序后的新头为什么必须用next_node临时保存cur.next我给你讲一个踩坑现场如果先把cur.next改成prev此时cur原来的下一个节点就再也找不到了因为你唯一能到达它的路径当前节点的next指针已经被覆盖。整个循环会卡死在原地或者进行一个奇怪的空转。所以“先保存后继、再改指针、再移动”这三步的顺序一个都不能错。为了更直观地理解拿1-2-3举例reverse_list过程如下步骤curprev处理后效果初始化1None还没动循环11None1.next Noneprev1cur2循环2212.next 1prev2cur3循环3323.next 2prev3curNone循环结束返回prev也就是3链表变为了3-2-1。整个逆序过程用的是节点本身不创建新节点所以额外空间是O(1)。3.3 关键操作三回文比较与链表恢复后半段逆序完成后原链表被切成两段从head到slow之前的“前半段”以及从reverse_list(slow)返回新头开始的“逆序后半段”。现在可以开始比较了。def is_palindrome_core(head): if not head or not head.next: return True # 找中点 slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 反转后半段 second_half_start reverse_list(slow) # 双指针比较 left head right second_half_start result True while right: if left.val ! right.val: result False break left left.next right right.next return result比较循环的条件为什么写成while right而不是while left关键在于奇数长度链表反转后半段后右半段会比左半段少一个节点。比如1-2-3-2-1反转后半段3-2-1后得到1-2-3此时右半段有3个节点。左半段从head开始123。右半段也是123注意因为3是中点被算进了右半段。比较3轮后right变成None结束。如果此时用while leftleft还会停在下一个节点比较就会出错。所以按照右半段的长度来循环是最稳的。如果你不想破坏原链表比较之后还需要做一次“恢复”把后半段再次逆序让链表恢复原状。恢复操作本质上就是再次调用reverse_list然后让前半段的最后一个节点的next指向恢复后的头部。这里有个小麻烦前半段最后一个节点是谁如果你在找中点时没有额外保存它恢复时就需要遍历一次前半段去寻找。一个更简单的做法是在刚才找中点时同时记下prev_slowdef is_palindrome_core_restore(head): if not head or not head.next: return True slow head fast head prev_slow None while fast and fast.next: prev_slow slow slow slow.next fast fast.next.next # 反转后半段 second_half_start reverse_list(slow) left head right second_half_start result True while right: if left.val ! right.val: result False break left left.next right right.next # 恢复原结构 prev_slow.next reverse_list(second_half_start) return result这里prev_slow保存了待反转段前一个节点也就是原链表前半段的尾部。恢复时把后半段再反转一次后挂回prev_slow.next链表就恢复了原样。这一步是很多教程容易遗漏的但面试官往往很看重——能主动恢复链表结构说明你理解了指针操作对数据的副作用。3.4 完整代码与执行流程把上面的逻辑拼起来我用Python给出一份可直接运行的整体实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def create_linked_list(vals): dummy ListNode() cur dummy for v in vals: cur.next ListNode(v) cur cur.next return dummy.next def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev def is_palindrome(head): if not head or not head.next: return True slow head fast head prev_slow None while fast and fast.next: prev_slow slow slow slow.next fast fast.next.next second reverse_list(slow) left head right second while right: if left.val ! right.val: return False left left.next right right.next return True def print_list(head): vals [] cur head while cur: vals.append(str(cur.val)) cur cur.next print(-.join(vals)) if __name__ __main__: tests [ [], [1], [1, 1], [1, 2], [1, 2, 2, 1], [1, 2, 3, 2, 1], [1, 2, 3, 4], [a, b, a], ] for vals in tests: head create_linked_list(vals) print_list(head) print(is_palindrome:, is_palindrome(head))这段代码的执行流程是创建链表 → 找中点 → 反转后半段 → 比较 → 返回结果。我在测试列表里包含了空链表、单个节点、双节点相同、双节点不同、偶数长度回文、奇数长度回文、非回文、字符型回文这8类典型用例。运行后应当得到True、True、True、False、True、True、False、True。4. 实操过程从最基本操作到完整可运行代码4.1 不带头结点 vs 带头结点的结构陷阱很多人学习链表时老师讲的头节点和头指针的概念容易搞混在回文判断里这直接影响代码边界。先明确一下带头结点的链表就是额外挂一个dummy哨兵节点作为表头真实数据从dummy.next开始不带头结点的链表head直接就是第一个数据节点。在我上面的完整实现里create_linked_list用了dummy节点来简化建表过程这在做算法验证时非常方便。但在LeetCode这类算法题中函数签名给的head往往是不带头结点的第一个节点也就是真正的数据节点。这就需要你在判断入口做好防护若head is None返回True空链表算回文。若head.next is None返回True单节点也算回文。两种情况的判断必须放在快慢指针之前否则会直接报错出现None.next访问。不带头结点的链表写起来需要额外警惕“空指针解引用”。快慢指针循环里之所以要写while fast and fast.next就是为了防止fast走到链表末尾后再加一步访问fast.next.next导致崩溃。4.2 基本操作热身指定位置插入、逆序、清空回文判断依赖的底层操作其实非常基础。如果你对指定位置插入、单链表整体逆序、清空链表这些常规操作不够熟练那道回文题基本写不顺。我建议写回文代码之前先把这几个基本操作练到闭眼能敲出来。指定位置插入核心是先找到目标位置的前驱节点。这里我用0表示“头部之前的位置”用链表长度表示“尾部追加”def insert_at_position(head, val, pos): dummy ListNode() dummy.next head cur dummy index 0 while cur and index pos: cur cur.next index 1 if not cur: raise IndexError(position out of range) node ListNode(val) node.next cur.next cur.next node return dummy.next注意保存cur.next的顺序如果先把新节点挂到cur.next再取原后继你就找不回原来的链表了。每次插入之前先画一张两个节点的接线图能帮你避免不少低级错误。清空链表操作在Python里最简单直接把head引用置为None就行因为垃圾回收会处理后续节点。但理解“游走删除”的逻辑仍然有价值例如在其他语言里你可能是用一个临时指针逐节点释放def clear_list(head): cur head while cur: nxt cur.next cur.next None cur nxt return None这个函数展示了链表遍历的通用骨架记录下一个节点处理当前节点再移动到下一个。学会了这个骨架逆序、查找、插入都能手到擒来。4.3 验证用例设计与边界测试写完了代码最怕的就是自我感觉良好。回文判断这个题边界情况特别多我给出一套自测用例清单用例描述输入期望结果空链表NoneTrue单节点5True双节点相同5-5True双节点不同5-6False偶数长度回文1-2-2-1True奇数长度回文1-2-3-2-1True奇数长度非回文1-2-3-4-5False全是相同值7-7-7-7-7True偶数长度非回文1-2-3-4False我强烈建议你把每个用例都打印出链表内容和判断结果来肉眼核对尤其要关注奇数长度下“中点被包含在右半段”这个行为。4.4 Python环境下的调试技巧链表问题在Python里排查起来有天然优势你可以直接打印节点值但打印时注意不要陷入死循环。如果逆序代码写错链表可能成环一打印就会无限输出把终端刷爆。我自己的调试习惯是写一个带“安全步数”的打印函数def print_list_safe(head, max_steps1000): vals [] cur head step 0 while cur and step max_steps: vals.append(str(cur.val)) cur cur.next step 1 if cur: vals.append(...CYCLE DETECTED...) print(-.join(vals))这样即使代码有环也不会让调试进程卡死。另一个有用的技巧是在快慢指针循环体内加断言每走一步就检查fast和slow是否已经相遇如果相遇说明链表有环或者检查fast.next是不是None。这些小工具会帮你把调试时间从半小时压缩到五分钟。5. 常见问题与排查技巧实录5.1 快慢指针边界奇数/偶数长度的坑快慢指针最容易被问倒的就是“当链表长度是偶数时slow到底停在哪个节点”。我再强调一次停在“右半段的第一个节点”而不是左半段的末尾。例如1-2-3-4循环结束时slow指向3。这个位置对于反转后半段来说是好事因为右半段从3开始左半段从1开始两个半段的长度刚好都是2。如果你不记得这个规律有一个笨办法在纸上画一个链表把slow和fast的移动过程一步步标注出来。我当年就是这么干过来的纸上推演一遍后几乎所有边界问题都能搞清楚。算法题不是靠背答案而是靠建立对过程的直觉。还有一个容易踩的点循环条件应该写成while fast and fast.next还是while fast.next and fast.next.next我建议用前者。前者在fast为空或fast.next为空时都会安全退出后者在链表较短时第一次进入循环就可能访问fast.next.next如果fast.next为空就会直接报错。5.2 逆序后指针丢失怎么找回来逆序操作中最经典的bug是“忘记保存后继节点”。我在第3.2节已经示范了正确写法但这里还想补充一个典型错误版方便你对号入座def reverse_list_wrong(head): prev None cur head while cur: cur.next prev # 错此时cur.next已被覆盖 prev cur # 无法再移动到原下一个节点 cur cur.next # cur.next现在是prev所以cur会往回走 return prev这段代码运行起来会出现两个结果要么形成环要么链表被“倒着走”回头部返回的prev并不指向链表尾部。在回文判断中这样的错误会让后续比较完全错乱。怎么排查这种问题当你发现打印链表时出现循环输出或者结果毫无规律第一时间检查三个点第一逆序函数里是否在修改cur.next之前保存了nxt第二循环结束时cur是否移动到了None第三返回值是否为原来链表的尾节点。这三个点逐一核对逆序问题基本就能定位。5.3 空链表、单节点、双节点这些特殊场面空链表和单节点这两个场景很多人在开头忘了处理导致程序在快慢指针阶段直接抛异常。其实处理非常简单就是加一个前置判断if not head or not head.next: return True双节点的时候比如5-5快慢指针循环只会执行一步slow到第二个节点5fast走到None。接着反转后半段后半段就是单节点5比较时left和right都指向值5相等返回True。这段流程短小适合作为最小用例来验证你的基本实现有没有跑通。如果链表元素全部相同比如7个7回文判断一定返回True。这种用例可以测试“不必要的比较”会不会出错也可以观察取中间位置和中点归属的规律。面试时可以用来验证边界条件的正确性。5.4 一条实用的自检清单我在实际辅导过程中总结了一份自检清单每写完一版回文判断代码我会按顺序问自己以下几个问题空链表和单节点是否已经先行返回True快慢指针循环退出时slow是否真的停在期望的位置偶数长度时右半段头部逆序函数修改指针前是否保存了下个节点比较循环用的是while right还是while left如果是while left奇数长度链表会多比较吗如果要求不修改原链表恢复代码是否把原链表后半段重新翻转并挂回了prev_slow.next测试用例是否覆盖了奇数、偶数、空、单节点、全相同五种典型场景这六个问题挨个过一遍回文判断的代码质量基本就稳了。它不是万能 checklist但覆盖了这道题90%的常见错误来源。我在实际写这道题时的体会是先画图再写代码。链表问题最怕脑子里一团浆糊就上手敲键盘。拿笔在草稿纸上画出1-2-3-2-1的节点用箭头标注slow和fast每一步的位置逆序时把指针变化画成三步你会在五秒内发现自己哪里理解不到位。回文判断本身是个综合应用题考查的其实是快慢指针和链表逆序两记基本功的串联配合。如果你把这两个基本操作练得足够熟练回文判断就是水到渠成。希望这篇文章能帮你少走弯路直接把最稳的方案写出来。