空间解法)
★ FEATURED ARTICLE 1. 为什么这道题值得仔细拆开做一遍回文链表是个很奇妙的题。第一次在 LeetCode 上看到 234 这个编号大多数人的第一反应是这题不是很简单吗把链表遍历一遍存到数组里然后双指针从头尾比较就行了。如果你也是这么想的那恭喜你你已经掉进了最常见的坑——LeetCode 234 真正的考察点不在于你知不知道回文的概念而在于你能不能在不借助额外存储的情况下只靠链表指针的移动就把问题解决掉。我当时刷到这题的时候是在某次模拟面试的场景里。前五分钟我用数组法写出来了心里还挺美。结果对面的人追问了一句如果链表的长度是五百万内存很紧张你还能用数组吗我才意识到数组解法本质上是把问题从链表平移到了数组并没有真正处理链表本身的特性。从那一刻起我决定把这道题的所有解法都过一遍尤其是那个 O(1) 空间复杂度的思路。今天这篇就当作是一次完整的复盘。这题适合谁看如果你是刚开始刷链表题目的新人建议从第 2 部分开始把三种解法的思路逐个看懂如果你已经有刷题基础可以直接跳到第 3 和第 4 部分那里面有不少细节是你在 LeetCode 的题解区不太容易一次看全的。2. 先从最直观的解法说起把问题从链表搬到数组2.1 数组复制法两分钟写出来但软肋很明显class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def isPalindrome(head: ListNode) - bool: vals [] cur head while cur: vals.append(cur.val) cur cur.next return vals vals[::-1]这个解法的逻辑几乎不需要解释先遍历一遍链表把每个节点的值按顺序存进一个 Python 列表然后比较这个列表和它的反转是否相等。在 Python 里vals[::-1]会创建一个新列表所以整个算法的空间复杂度是 O(n)时间复杂度也是 O(n)。你要是只追求能通过所有测试用例这个解法确实够了。因为 LeetCode 官方给的数据范围只到节点数的量级在几千到几万之间内存完全不存在压力。但这是典型的靠语言特性绕过了链表问题你没有任何一步操作是指针层面的。面试官一眼就能看出来你没有真正理解链表这种数据结构的操作方式。另外一个隐藏细节是vals[::-1]在 Python 里创建的是新的列表对象而不是原地反转。如果你写vals.reverse()再比较那又得先复制一份原列表。在这个场景下简洁写法没问题但你在心里要清楚所谓的 O(n) 空间不是一个抽象概念它具体意味着你要为整个链表的长度多分配一份内存。2.2 递归解法代码很漂亮但系统栈是隐形成本递归解法的思路也很直接用一个外部指针从前向后走递归的调用栈从后往前走两者在中间相遇时逐个比较。def isPalindrome(head: ListNode) - bool: front head def check(node): nonlocal front if node: if not check(node.next): return False if front.val ! node.val: return False front front.next return True return check(head)这段代码初看很惊艳递归天然地帮你完成了先走到链表尾再从尾向头回溯的过程。每次递归返回的时候front指针从头向中间移动node指针从尾向中间移动两者在中间位置完成所有配对比较。但问题是递归的深度和链表长度是严格绑定的。链表有多长函数调用栈就有多深。在本地测试一个十万节点的链表程序就会因为递归深度超出限制而崩溃。就算你把递归上限调高系统栈的消耗依然存在只是不再报错而已。所以这个解法在实际生产环境中几乎不可用它更适合作为理解递归回溯和指针协同的教学示例。我在学这个解法的时候最大的收获是递归解决链表问题很直观但代价是隐形的。你看到的代码只有几行但你不知道这几行代码背后压了多少层栈帧。在嵌入式或者内存敏感的系统中这种隐形成本往往是致命的。2.3 复杂度对比先别急着追求最优解三种解法在动手编码之前应该有一个全局认知。我把它们放在一张表里对比解法时间复杂度空间复杂度代码量核心思路数组复制法O(n)O(n)最少空间换时间绕开指针操作递归法O(n)O(n)系统栈最少利用调用栈实现反向遍历快慢指针反转O(n)O(1)适中原地反转后半段直接比较很多人做题有个误区只看时间复杂度忽略空间复杂度。但这道题的精髓恰恰在于空间复杂度。你如果真的想在面试中展示自己的链表功底最终还是要落到快慢指针加反转这个解法上。我个人的学习节奏建议是第一遍刷题时先写数组复制法确保思路没有遗漏第二遍再尝试递归法体会系统栈的代价第三遍才去啃 O(1) 空间的快慢指针解法。每多学一个解法你对链表指针操作的理解就会深一层。3. O(1) 空间的正解快慢指针定中点再反转后半段3.1 快慢指针为什么能准确地找到中点快慢指针是链表题目里一个极其经典的技巧。思路是slow指针每次走一步fast指针每次走两步。当fast走到链表末尾时slow刚好到达链表的中点。为什么这个逻辑成立假设链表长度为 n。fast走完整个链表需要的步数是 n 或者 n-1 步取决于 n 的奇偶性。slow走的步数恰好是fast的一半所以slow停下的位置就是中点。严谨地说偶数长度的链表slow落在后半段的第一个节点奇数长度的链表slow落在正中间的那个节点。这个特性后面在比较阶段会用到。找到中点之后整个问题的结构就变了一个完整的回文链表前半段的节点顺序恰好是后半段节点顺序的反转。也就是说只要我把后半段链表原地反转然后从头部和反转后的后半段头部分别开始比较一对一比对值相等就能判断是否回文。整个过程只需要几个指针变量不需要额外的数据结构空间复杂度 O(1)。3.2 反转后半段时指针到底怎么切找到中点之后下一个动作是把slow指向的这个节点作为后半段的起点对后半段做单链表反转。这里最容易犯的错误是搞不清楚反转结束后prev到底指向什么。prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt这段循环结束之后prev指向的是原链表最后一个节点也就是反转后的后半段链表的头节点。cur已经变成None。后半段原来的链表关系全部被改写了。这里有一个特别值得注意的点反转操作是原地进行的它直接破坏了原链表的结构。如果题目只要求判断回文而不要求保持原链表那么破坏之后无所谓。但如果面试官要求你判断完之后恢复原链表你需要在比较结束后再做一次反转恢复。这个需求在真实工程中非常常见我后面会单独展开讲。3.3 完整代码逐行解读把找中点、反转后半段、比较三段逻辑串起来就得到了这个经典解法class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def isPalindrome(head: ListNode) - bool: if not head or not head.next: return True # 1. 快慢指针找中点 slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next # 2. 反转从 slow 开始的后半段 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt # 3. 前半段从头开始后半段从 prev 开始逐个比较 left, right head, prev while right: if left.val ! right.val: return False left left.next right right.next return True注意第 1 步中快慢指针循环的条件是while fast and fast.next这个条件处理了奇数和偶数长度两种情况奇数长度比如1 - 2 - 3 - 2 - 1当fast走到最后一个节点时fast.next是None循环结束slow停在 3 这个中间节点。偶数长度比如1 - 2 - 2 - 1当fast走到None时循环结束slow停在第二个 2 上也就是后半段的起点。在实际编码中这个循环条件是最容易写错的地方。有人会写成while fast.next and fast.next.next在某些情况下也能跑通但它和标准写法对中点位置的语义完全不同不推荐这么写。比较阶段我用的循环条件是while right也就是以后半段为准。这很关键因为在奇数长度时前半段比后半段多一个节点多出来的正好是中间节点而中间节点的回文对称性天然成立不需要参与比较。如果循环条件写成while left and right最终结果也一样但判断语义不如while right清晰。3.4 一个完整的执行过程演示只看代码可能会有点抽象我拿一个具体的例子跑一遍完整流程。假设链表是1 - 2 - 3 - 2 - 1第一步快慢指针初始slow 1, fast 1第一次循环slow 2, fast 3第二次循环slow 3, fast 1此时 fast.next 为空循环结束slow 指向 3。第三步反转后半段从 3 开始链表变成1 - 2 - 3 - 2 - 1 后半段反转后实际是3 - 2 - 1注意这里原来的 3 在反转之后依然是前后两段的交界点但它的next指针已经被改成了None。现在左指针left从 1 开始右指针right也就是prev从原尾部 1 开始left1, right1相等left2, right2相等left3但 right 已经是None循环结束返回 True。中间节点 3 没有被比较这是符合回文定义的因为回文只需首尾配对。再看一个非回文的例子1 - 2 - 3 - 4快慢指针结束后 slow 指向 3。反转后半段3 - 4 变为 4 - 3。比较阶段 left1, right4 不等返回 False。逻辑正确。4. 把这道题写对最有必要盯住的四个细节4.1 快慢指针循环条件的前后顺序快慢指针循环里的条件while fast and fast.next是有讲究的。fast在前面fast.next在后面这个顺序绝对不能反过来。因为如果fast已经变成None再访问fast.next就会抛出空指针异常。这个错误在所有链表题里都很常见但我发现不少人在写 234 这道题时尤其容易踩坑因为这里的循环退出条件是在整个算法中最容易出现歧义的地方。我自己的经验是写这个循环之前先在纸上画一条奇数链、一条偶数链把slow每次移动的位置标出来再决定条件怎么写。一旦你真正理解了奇偶两种情况的终止时机这个条件就不会再忘。4.2 空链表和单节点两个极端情况LeetCode 的测试用例里包含空链表和单节点链表。从语义上说空链表没有内容算不算回文呢在绝大多数题目设定里None被认为是回文的。单节点链表正着读反着读都一样也是回文。所以在函数开头加一个判断if not head or not head.next: return True这个判断同时处理了空链表和只有一个节点的链表。少写这个判断第一个用例就会报错多写这行则能避免后续所有快慢指针逻辑在极端情况下的风险。4.3 比较结束之后要不要恢复原链表前面提过快慢指针解法在比较过程中会把后半段链表原地反转。如果题目的要求只是判断是否为回文这个破坏是允许的。但在真实系统里你通常不会希望一个只读的判断操作把传入的数据结构给改了。所以我在实际开发时有一个习惯判断完回文之后顺手把后半段再反转回来。怎么恢复很简单在比较结束后调用一次和第二步相同的反转函数把prev作为头节点传进去反转后的结果又会重新拼回原来的链表结构。代价是常数级的时间开销换来的是函数没有副作用。面试时主动提到要不要恢复原链表是一个加分动作因为绝大多数候选人根本不会想到函数修改入参这个问题。4.4 本地自测用例清单我在本地一般会用这些用例去验证完整性和边界场景输入预期结果空链表[]True单节点[1]True两个相同节点[1,1]True两个不同节点[1,2]False奇数长度回文[1,2,3,2,1]True偶数长度回文[1,2,2,1]True奇数长度非回文[1,2,3,4,5]False全部相同节点[1,1,1,1,1]True其中[1,2,2,1]和[1,2,3,2,1]这两个用例是重中之重它们分别覆盖偶数长度和奇数长度的情况能一次性检验快慢指针找中点和比较循环条件的正确性。5. 从这道题延伸出去的链表解题模型5.1 快慢指针不止能找中点回文链表只是快慢指针的应用场景之一。同一个技巧还能解决很多链表问题比如判断链表是否有环、寻找环的入口、寻找链表的倒数第 k 个节点等。它们的底层逻辑是一样的用两个速度不同的指针在链表上运动通过它们之间的相对位置关系来推断链表的结构性质。如果你想把这一类题一次性吃透建议把141. 环形链表、142. 环形链表 II、876. 链表的中间结点这三道题和 234 放在一起刷。你会发现它们的核心代码高度相似都是快慢指针只是退出条件和指针之后的操作不同。刷完这四道题快慢指针模型基本就固化了。5.2 反转链表的三只手反转链表是这道题的关键前置技能。标准的迭代反转需要三个指针prev、cur、nxt。很多初学者会疑惑为什么需要nxt因为如果不先把cur.next保存下来反转之后你永远找不到原链表中剩下的部分了。prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt这个模式值得练到肌肉记忆。不只是回文链表206. 反转链表、92. 反转链表 II、25. K 个一组翻转链表全部建立在这个基础操作之上。一旦反转操作熟练了234 就只是找中点加反转加比较的拼装题。5.3 空间和时间权衡的思维习惯数组复制法 O(n) 空间快慢指针法 O(1) 空间两者都能通过 LeetCode但在系统设计层面这个差异往往就是方案能不能落地的分水岭。我在某个嵌入式相关的项目里处理过类似需求链表的节点数由数据采集频率决定高峰期能达到数十万而设备内存只有几百 KB。如果用数组复制法光存储节点值就需要分配近 MB 级内存直接超预算改成快慢指针加反转的思路只需要几个指针变量内存占用可以忽略不计。这道 LeetCode 题在面试之外的工程价值恰恰体现在这里。所以刷题的时候不妨多想一步这个解法的空间开销能不能压缩压缩之后代码是否依然可读在真实系统里性能和代码可维护性需要同时考虑而不是单纯追求时间复杂度最优。6. 我复盘完这题最想提醒你的一件事所有链表类的题目核心就两个字指针。而 234 这道题的神奇之处在于它把链表的遍历、快慢指针、反转、双指针比较四个基本功全部考核了一遍。我见过一些人背下了解题模板却在面试时因为忘记了反转之后要恢复链表而被追问到卡壳也见过一些人用数组法通过了 LeetCode却完全说不出快慢指针方案的存在。如果你只看一个知识点那我建议你把快慢指针找中点这一步彻底弄明白。它不光是回文链表的关键也是后续大量中等难度链表题的基础。画图、写用例、打断点调试怎么都不过分。真正理解了这一步回文链表这道题才算是你的而不是 LeetCode 的。
阅读完成 · 觉得有帮助？
