判断一个序列是不是回文在数组里就是两个指针往中间怼三行代码搞定。但同样的问题放到单链表上很多刚练完链表基本操作的同学第一反应是这有什么难的结果上手一写要么空间爆了要么指针断了要么直接死循环。这个题我前前后后给不同的人讲过无数遍——它表面上考回文实际上考的是你对单链表最核心三件事的理解怎么找中间节点、怎么就地反转、怎么处理边界。这篇就来把单链表回文结构这件事从头到尾拆开。先聊清楚为什么链表做回文判断别扭然后过一遍四类主流解法重点放在面试和考试里最常要求的快慢指针反转法附完整Python代码和逐行解释。最后把我实际调试过程中踩过的坑整理成一份速查表包括奇偶长度处理、无头结点的链表、恢复原链表、测试用例构造这些细节。适合刚学完单链表基本操作、准备面试、或者正在做数据结构实验的同学直接参考。1. 回文结构先聊明白单链表为什么在这个问题上别扭1.1 回文判断在数组里有多简单回文结构就是正着读和倒着读一样。比如 1 - 2 - 3 - 2 - 1 这条链表从头到尾和从尾到头读出来的序列完全一致它就是回文结构而 1 - 2 - 3 - 3 - 1 就不是因为倒过来是 1 - 3 - 3 - 2 - 1。这个定义本身没什么可说的关键在判断手段上。如果是数组判断方法写到烂两个下标一个从0往右走一个从len-1往左走逐个比较直到相遇。因为是随机访问结构数组可以在O(1)时间内拿到任意位置的元素整个判断过程O(n)时间、O(1)空间干净利落。这也是为什么很多人在初学链表时会低估回文判断同样的逻辑我能不能也用两个指针从两端往中间走这就触及单链表最核心的限制了。1.2 单链表的单向性带来的三个麻烦单链表每个节点只存了一个next指针。这意味着三个事情。第一从尾部反向遍历做不到。你没有prev指针走到最后一个节点之后想回到倒数第二个节点只能重新从head开始走一遍。这就像你只拿到了一条单行道的地图开到终点之后不能掉头。第二无法O(1)访问中间节点。数组可以直接通过下标算出中点链表必须一个节点一个节点数过去。数到中点需要O(n/2)的时间这个成本本身不可忽略也是后面快慢指针方案存在的意义。第三比较过程中如果动手改了链表恢复起来麻烦。为了对比首尾很多解法需要把链表拆成两段甚至反过来比较完之后链表已经被改得面目全非。在面试场景下通常要求要么不改原链表要么比较完恢复原样这就对实现细节提出了额外要求。这三个麻烦合在一起让单链表回文判断从一个简单的遍历问题变成了一个综合考察节点操作能力的题。你真正在动手解决的不是回文本身而是怎么在单向结构里完成从两端向中间的访问。2. 解法全景四类思路逐个过一遍2.1 辅助数组法五分钟写出但空间吃亏最直接的办法遍历一次链表把所有节点的值按顺序放进一个数组然后用数组的判断方法。def is_palindrome_array(head): values [] p head while p: values.append(p.val) p p.next left, right 0, len(values) - 1 while left right: if values[left] ! values[right]: return False left 1 right - 1 return True这个方法的优点是不用动链表结构边界条件也很好处理空链表和单节点直接返回True就行。缺点也很明显O(n)的额外空间。面试时如果面试官追问一句能不能把空间优化到O(1)光会这一种写法是不够的。不过我得说句公道话在工程里如果你的链表本身数据量不大辅助数组法完全够用而且可读性最好。不是所有场景都追求极致空间很多人一上来非要用快慢指针结果写出bug反而得不偿失。先能跑再优化这是我实际调试中比较认同的顺序。2.2 栈辅助法比较自然的O(n)空间解另外一个朴素思路是借助栈的先进后出特性来实现反向遍历遍历链表把所有节点值压栈然后把栈顶元素依次弹出同时再遍历一次链表逐个对比。def is_palindrome_stack(head): stack [] p head while p: stack.append(p.val) p p.next p head while p: if p.val ! stack.pop(): return False p p.next return True辅助数组法和栈辅助法空间复杂度一样都是O(n)。时间上也都是O(n)。差别在于数组法用两个下标从两端向中间收拢栈法用后进先出天然实现了从尾部开始访问。这道题用栈其实是从逻辑上最贴合回文定义的——回文就是正着读和倒着读一样而倒着读正是栈的看家本领。有一个小优化技巧可以先用快慢指针走到中点的位置再把后半段入栈弹出时只跟前半段比较。这样栈的空间只有n/2虽然量级还是O(n)但常数小了一半。这个变体在笔试里偶尔会作为进阶要求出现。2.3 递归法思路优雅但实际不推荐递归法基于这样一个事实递归调用天然保存了回来的路径。用一个外部指针从头部开始递归函数一路走到链表末尾然后在回溯过程中和外部指针比较。def is_palindrome_recursive(head): front head def recur(node): nonlocal front if node is None: return True # 先走到链表末尾 if not recur(node.next): return False # 回溯时与front比较 if front.val ! node.val: return False front front.next return True return recur(head)这个写法在思路上很优雅但是实际我不推荐。原因有三个递归深度等于链表长度链表一长栈就爆了每层递归都有函数调用开销实际跑起来比迭代版本慢不少更重要的是它那个front指针的移动时机非常容易写错初学者调试起来很痛苦。如果只是为了理解调用栈天然是反序的这个思想可以写一遍玩玩但正式场合别用它。2.4 快慢指针链表反转面试想看的那个解终于说到重点了。快慢指针反转法把空间优化到了O(1)而且每一部分都是链表基本功的体现。核心思路一句话把链表从中间拆成两半把后半段原地反转然后两个半段从头开始逐个比较。为什么前半段不用反转因为前面说过单链表没法从尾向前但反转之后就可以把后半段的尾部变成后半段的头部这样从两个头部同时出发比较就等价于一个从头、一个从尾往中间逼近了。目标是O(1)空间所以必须就地改指针这是整个方案里最见功夫的地方。后面我会用一整节详细拆这个方案这里先把四个解法的特点整理成一张表。解法时间复杂度空间复杂度是否改动链表适用场景辅助数组法O(n)O(n)否数据量小追求可读性栈辅助法O(n)O(n)否逻辑直观笔试快速过递归法O(n)O(n)递归栈否理解思想不建议实战快慢指针反转O(n)O(1)是可恢复面试、竞赛、严格要求空间的场景表里是否改动链表这一列值得多说两句。辅助数组和栈都不动链表递归也不动链表只有快慢指针反转是动了next指针的。如果题目明确要求判断完链表保持原样那你需要在比较完之后把后半段再反转一次接回去。这个恢复操作我在第4节会专门讲。3. 快慢指针反转法完整实现含Python代码3.1 三步走找中点、反转、比对整个算法拆成三步。第一步找中间节点。用两个指针同时从头出发慢指针每次走一步快指针每次走两步。快指针到尾时慢指针正好在中间附近。这里有一个细节必须讲清楚循环条件到底是while fast and fast.next还是while fast.next and fast.next.next决定慢指针最终落在哪个节点上。我推荐后者。用后者时链表长度为奇数如1-2-3-2-1slow停在正中间节点3链表长度为偶数如1-2-2-1slow停在左半段的最后一个节点也就是第一个2。无论奇偶slow.next都是后半段的起点。这样设计的好处是反转操作只需要从slow.next开始整条链表的连接关系最清晰。如果用while fast and fast.next偶数长度时slow会直接落在右半段的第一个节点上后续反转的边界写起来容易绕晕。第二步反转后半段。这是单链表逆序这个基本功的现场应用。从slow.next开始用一个prev记录已反转部分一个cur指向当前节点一个nxt暂存下一步位置逐个把next指向前一个节点。三步指针法的口诀就是先存后路再改指向最后移动。第三步逐节点比较。左半段从head开始右半段从反转后的新头部开始两个指针同步往后走。只要右半段没走完就比较两个节点的值。这里不用管左半段是否还有剩余因为右半段的长度一定不超过左半段奇数长度时右半段还少一个中间节点所以用右半段是否为空作为循环条件是安全的。3.2 完整实现代码与逐行解释class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def is_palindrome(head): # 空链表和只有一个节点的链表天然是回文 if head is None or head.next is None: return True # 第一步快慢指针找中点 slow head fast head while fast.next and fast.next.next: slow slow.next # 慢指针每次走一步 fast fast.next.next # 快指针每次走两步 # 此时 slow 在中点奇数或左半段末尾偶数 # slow.next 就是后半段的起点 # 第二步反转后半段 prev None cur slow.next while cur: nxt cur.next # 先保存下一步要处理的节点 cur.next prev # 把当前节点的next指向前一个节点 prev cur # prev 前移 cur nxt # cur 前移 second_half prev # 反转后的新头部 # 第三步逐节点比较 left head right second_half while right: if left.val ! right.val: return False left left.next right right.next return True逐行过一遍。第一行到第五行是节点定义这个不多说。is_palindrome函数开头先做特判。注意我这里的特判是head is None or head.next is None有人会漏掉head.next这个条件直接导致后面访问head.next.next时出问题——空链表和单节点链表在你动手写循环之前就必须挡掉。找中点的循环条件while fast.next and fast.next.next。以1-2-3-2-1为例初始slow和fast都在节点1第一轮后slow到2、fast到3第二轮后slow到3、fast到1此时fast.next是None循环结束slow停在正中间正确。再以1-2-2-1为例第一轮后slow到第一个2、fast到第二个2此时fast.next存在但fast.next.next是None循环结束slow停在左半段末尾的第一个2也正确。这个条件比while fast and fast.next更好用的原因就在偶数长度场景下后一种写法会让slow落在右半段的第一个节点上后续split和反转的逻辑反而不直观。反转部分的三步指针法我第一次学的时候总觉得为什么要多一个nxt变量。后来自己写断链bug写多了才明白如果不先把cur.next存下来改完指向之后就再也找不到原来那个下一个节点了。链表操作里绝大多数指针丢失都是这个原因。比较部分用一个while right是因为右半段的长度要么等于左半段要么比左半段少一个奇数长度时的中间节点。以右半段为基准既可以完整覆盖所有需要比较的节点对又不会出现空指针。3.3 边界条件清单空表、单节点、奇偶长度、无头结点老规矩把边界条件一项项列清楚。空链表。题目如果不特别说明空链表按回文处理。很多同学在实验课上写这个题常常忘记空表判断导致head.next直接抛AttributeError。我建议把空表和单节点两个判断合并成一个if代码更干净。单节点链表。只有一个节点正着读倒着读都是它自己必为回文。如果不特判快慢指针循环虽然不会出错但后面反转的cur slow.next是None反转循环直接跳过second_half是None比较循环也跳过最后返回True。逻辑上碰巧正确但这是靠运气不是靠设计。特判写清楚逻辑才直观。奇数长度。比如1-2-3-2-1。中间节点3不需要参与比较因为它的对称位置就是它自己。算法里反转后半段后得到2-1左半段从头开始是1-2比较两组就结束3被自然跳过不需要单独处理。这个中间节点天然不用比的性质是快慢指针方案的一个隐含好处。偶数长度。比如1-2-2-1。前半段是1-2后半段是2-1反转后半段得到1-2两组节点完全一一对应全部参与比较。偶数长度下没有多余的中间节点每一个节点都在配对范围内。无头结点的链表。这里要说明一下头结点和头指针是两个概念。很多教材里的链表实验会有一个不存数据的头结点真正的数据从第二个节点开始。如果题目给的是带头结点的链表那head本身指向的是那个哑节点遍历和比较时需要从head.next开始。但上面的代码默认了链表是不带头结点的也就是head直接指向第一个数据节点。比赛和面试环境里大多数是这种形式如果你在实验课作业里遇到了带头结点的情况只要把每个用到head的地方替换成head.next即可算法本身完全不用变。这个多一个哑节点的小差异恰恰是很多人在实验报告里写糊涂的地方。循环单链表。如果是循环单链表情况就完全不同了。因为尾节点的next指向头节点而不是None快慢指针的判断条件不能再用fast.next是否为None来判断而是要用是否回到起点来判断复杂度一下子上去不少。我见过有人把循环单链表和普通单链表混在一起写结果程序陷入死循环。回文结构这个题绝大多数情况下讨论的都是非循环的单链表遇到循环的版本先确认清楚再动手。4. 实操踩坑实录指针丢失、恢复链表与边界排查4.1 反转之后链表断了指针丢失的典型现场我在给同学debug时见过最多的错误是把反转写成这样while cur: cur.next prev prev cur cur cur.next # 错误此时 cur 已经不再是原来的下一个节点了这个错误非常经典。第一轮循环里执行完cur.next prev之后cur.next指向了prev原来链表里cur后面那个节点就找不到了。这时候再执行cur cur.nextcur变成了prev整个链表的后半段还没反转完就丢了。正确写法是把nxt cur.next放在改变指向之前。提示只要你发现反转后的链表比较结果出错先不要急着查比较逻辑把反转循环里先存nxt再改指向的顺序检查一遍。我在实际排查中发现至少一半的错误都出在这一步。这个坑的排查经验是如果你发现程序比较到一半报错或者比较结果莫名出错先检查反转循环里有没有在cur.next prev之后再碰cur.next。一旦反转时丢了节点后半段链表就断了后面比较时要么长度不对要么直接None指针。4.2 链表被改了面试官要求恢复原链表怎么办快慢指针反转法在判断结束之后原链表的后半段是反转过的状态。比如1-2-3-2-1判断完之后链表变成了1-2-3-1-2前半段原样后半段反转后接在中间节点后面。等等严格说后半段反转后slow.next还指向原来第二个2但这个2的next已经断了整体结构确实不是原来的样子。如果题目要求链表必须保持原样常见做法是判断完再把后半段反转一次。也就是从second_half这个头开始用同样三步反转再转回来然后接到slow后面。# 恢复链表把后半段再反转一次 prev None cur second_half while cur: nxt cur.next cur.next prev prev cur cur nxt slow.next prev return True # 此时回文结果已经确定恢复不影响返回值注意恢复的时候还要把slow.next重新接回prev。很多人最后一步只反转了第二段忘了把它接回slow后面结果链表虽然恢复成两段独立的样子但整体是断开的。我按1-2-3-2-1实际跑过一遍恢复逻辑第一次反转后得到second_half为1-2恢复时从1开始反转最终slow.next接到2整条链表变回1-2-3-2-1完全复原。第二种情况如果题目没要求保持原样只是不希望额外占空间那判断完直接返回True或False就好链表保持反转后的状态在多数场景下可以接受。还有第三种情况如果题目要求完全不改链表本身那就回到辅助数组或栈的思路。这也解释了为什么我说先能跑再优化拿到题目先确认清楚要不要保持链表原样如果要O(n)空间的方案反而更省心不用承担恢复逻辑出错的风险。4.3 无头结点、循环链表这些变体如何排查无头结点链表的问题上面说了主要是判断范围。我用过一个笨办法快速定位先把链表完整打印一遍确认第一个节点的值是什么。如果预期第一个数据值是3但打印出来有哑节点的0或者其他占位值那就是带头结点的情况没处理。打印调试在这种指针问题上比任何日志工具都管用。循环链表的最大风险是死循环。快慢指针找中点那步循环条件依赖fast.next为None来终止但循环链表里没有None只有回到头节点。如果你不确定题目给的链表是不是循环的可以先遍历一遍同时用哈希集合记录已经访问过的节点地址一旦出现重复地址就说明有环。实际比赛里写这种题的人不多遇到的话优先用哈希集合验证保证不会死循环。4.4 常见问题速查表我把实际操作中常遇到的问题整理成一张表方便你排查时对照。症状可能原因解决办法判断结果永远是False反转后半段时丢了节点比较长度不对检查反转循环里是否先保存nxt再改指向AttributeError: NoneType has no attribute val空链表或单节点未特判函数开头判断head is None或head.next is None偶数长度时结果错误快慢指针循环条件写成了while fast and fast.next改用while fast.next and fast.next.next比较后链表形状变了反转后半段没有恢复判断完再反转一次并接回slow.next带头结点链表结果错误遍历时没有跳过哑节点从head.next开始遍历和比较程序疑似死循环误把循环链表当普通链表处理用哈希集合记录节点地址验证是否循环这张表里的前三条是出现频率最高的。我自己带过的同学里十个写这个题的有四五个会中第一条的招。第二条和第三条往往同时出现因为很多人拿到题第一反应是写while fast and fast.next然后用slow作为右半段起点结果偶数长度时总会多比较一个节点或者漏一个节点。5. 从回文这道题看链表的三个基本功5.1 快慢指针不只是找中点很多人是在回文判断这道题第一次接触快慢指针。实际上它的用处远不止于此找链表中间节点、判断链表是否有环、找环的入口、找两个链表的交点等等都是快慢指针的经典场景。拿判断是否有环来说快指针每次走两步、慢指针每次走一步如果链表中存在环快慢指针最终一定会相遇这是一个数学上可以严格证明的结论。我自己的学习建议是与其把快慢指针当做一个孤立技巧去背不如把它理解成利用速度差制造位置差的思想。快慢指针的真正价值是在O(n)时间内只遍历一次就能拿到需要的中间位置信息而不是像数组那样靠下标随机访问。5.2 就地反转实验课到面试题的距离单链表逆序是数据结构实验课的经典作业回文判断里就现场用到了它。这也算是一个提醒实验课里那些看起来没什么用的基本操作其实是很多面试题的地基。你可以在实验课的时候把在指定位置插入建立单链表、单链表的清空这些基本操作好好练熟建立链表、清理链表、逆序链表三个动作熟了之后回文判断基本就是它们的组合。比如构造测试用例这一步我自己经常写一个build函数把一个Python列表转换成链表方便批量测试不同长度的回文和非回文数据def build_linked_list(values): dummy ListNode() cur dummy for v in values: cur.next ListNode(v) cur cur.next return dummy.next测试的时候print(is_palindrome(build_linked_list([1, 2, 3, 2, 1]))) # True print(is_palindrome(build_linked_list([1, 2, 2, 1]))) # True print(is_palindrome(build_linked_list([1, 2, 3, 3, 1]))) # False print(is_palindrome(build_linked_list([]))) # True print(is_palindrome(build_linked_list([1]))) # True这个build函数其实就对应了在指定位置插入建立单链表的实验要求只是用了尾插法。如果你日常有清理内存的需求Python里把head重新赋值为None就能让整个链表交给垃圾回收C语言实现时则要逐个节点free这也是单链表的清空在实战里的意义。5.3 测试用例怎么构造别在单链表上踩循环陷阱构造测试用例时我有一个固定建议至少准备五组数据。空链表、单节点、偶数长度的回文、奇数长度的回文、非回文。这五组覆盖了回文判断的所有分支。我自己在面试前的练习里还会额外加一组带负数或者重复值的数据确保比较的是值而不是地址排查指针问题时不会因为值恰好相等而掩盖错误。再有一个小经验如果项目里可以打印链表不要只打印值要把地址或者下标一起打印出来。回文判断这个题出错大多出在指针关系上光看值看不出问题。打印出(节点地址, 值, next地址)三元组反转前后各打一遍哪里断了清清楚楚。最后说点我自己的习惯。这个题我最早是在大学实验课上遇到的当时我用辅助数组法交的差老师问我能不能优化空间我卡了半天没答上来。后来准备面试时把快慢指针反转法写熟练之后才意识到这个题真正想考察的是你能不能把一个看似需要双向访问的问题用单向结构的基本操作组合出来。链表这个东西操作就那几样——遍历、插入、删除、反转但把它们组合起来的灵活性决定了你能解多难的问题。练这个题的时候别急着背答案试着把每一步为什么要这么写讲清楚讲得明白才算真会。
