企业官网建设流程全解析

链表这种数据结构，最难受的地方就是不能像数组那样按下标随机访问。想回头看前一个节点？只能重新从头再遍历一遍。234题“回文链表”考的正是这根软肋：给你一个单链表的头节点，判断整条链表的节点值序列从头到尾和从尾到头读是否一致。题目本身一句话就能说清，但进阶要求很利索——时间复杂度 O(n)、空间复杂度 O(1，直接把“转成数组再比较”这种省事解法堵死了。

我最早刷这道题的时候，第一反应就是数组，觉得这么简单的题有什么好考的。写完一提交，用时没问题，可一看空间消耗就有点心虚。后来把快慢指针和链表反转练成肌肉记忆再回头看，才意识到这道题真正值钱的地方在于：它把“定位中点”、“原地反转”、“双指针比较”三个高频知识点串成了一整条解题链路。适合刚学完链表基本操作的人检验指针熟练度，也适合准备技术面试、想系统复习链表双指针套路的人。把这一题吃透，收获的不是一个孤立答案，而是一套可以迁移到不少同类题上的通用手艺。

今天这篇就来完整拆解这道题：先讲清楚题目到底在考什么，再做三套方案的对比选型，然后把快慢指针和链表反转的原理一步步推一遍，最后附上可直接抄作业的代码，以及我实际踩坑、排查、被追问后总结出来的经验。

1. 题目拆解与三套方案的取舍

1.1 链表回文判定的真实难点

先明确一个基础定义。回文序列就是正着读和倒着读完全一样的序列，数组里判断回文非常简单：左指针从下标 0 出发，右指针从数组末尾出发，两边向中间走，一边走一边比较值，出现不相等就返回 false，直到两个指针相遇。

单链表的麻烦在于它没有“前驱指针”，每个节点只知道自己后面是谁，不知道自己前面是谁。也就是说，右指针天然不存在。你想从链表尾部往前移动，唯一的办法是每次都从头节点重新遍历，那样时间复杂度立刻变成 O(n²)，根本不可接受。

那能不能把链表倒过来读呢？可以，但“倒过来读”本身就是一道子题——链表的反转操作。于是这道题的核心矛盾就变成了：如何在一次 O(n) 的遍历，且不借助额外线性空间的条件下，把“从尾到头比较”这件事做出来。想明白这个矛盾点，下面三套方案各自的取舍就很清楚了。

1.2 转数组、递归、快慢指针到底选哪个

先说最直觉的方案 A：把链表遍历一遍，把所有节点值放进数组或动态数组里，然后按数组的回文判断方式用双指针比较。这个方案代码最短、最容易写对，也最容易讲清楚。代价是额外空间为 O(n)，和题目要求背道而驰。如果在面试场景里主动写这个，大概率会被追问一句“能不能不用额外空间”，然后你就得现场换方案。

再看方案 B：递归。思路是利用系统的函数调用栈来“记住”每个节点的信息。递归不断向右走到链表末尾，回溯的时候再做比较。一个标准写法长这样：

def check(head, cur): if cur is None: return True if not check(head, cur.next): return False if head.val != cur.val: return False return True

原理上，递归调用栈天然就是一个逆序访问链表的工具，函数走到最深的一层再往回弹，每一层都能和当前从外面传进来的指针做比较。但问题在于递归深度等于链表长度，空间同样是 O(n)，而且链表一旦很长就容易被系统栈深度限制。所以它能工作，但不满足进阶要求，也不是这里的最优解。

方案 C 就是本文的正解：一次遍历用快慢指针找到链表的中点，把中点之后的后半段链表就地反转，然后从原链表头部开始和反转后的后半段逐节点比较，一直比到后半段结束。整个过程只有几个指针变量的额外空间，时间复杂度 O(n)，正好命中进阶要求。它的缺点是实现细节比前两个方案多，快慢指针的边界条件容易写错，反转链表时一个不小心就会断链。

三个方案横向一摆，结论很明显：要同时满足题目的时间复杂度和空间复杂度要求，方案 C 是唯一能站得住脚的答案。而且它把“找中点”和“反转链表”这两个链表题里的高频基本操作组合到了一起，练熟这一题，等于一次复习了两项核心技能。

2. 核心原理：快慢指针与链表反转是怎么配合的

2.1 快慢指针定位中点的一步步推导

先聊快慢指针。所谓快慢指针，就是两个指针从同一个位置出发，一个每次走两步，另一个每次走一步，利用速度差在链表中产生“位移差”。由于快指针的速度是慢指针的两倍，当快指针到达链表末尾时，慢指针恰好走了大约一半的路程，也就自然落在了链表中点的附近。

边界情况要怎么处理？我推荐一个特定的初始化方式：让慢指针从 head 出发，快指针从 head->next 出发，循环条件是while (fast && fast->next)。停下来时的位置很有规律，我用两个例子走一遍。

链表长度为 4 时，节点是 1-2-3-4。初始 slow 在 1，fast 在 2。第一次循环：fast 非空且 fast->next 非空，slow 走到 2，fast 跳到 4；第二次判断：fast 是 4，非空，但 fast->next 为空，循环结束。此时 slow 停在 2，正好是前半段的最后一个节点。

链表长度为 5 时，节点是 1-2-3-4-5。初始同样 slow 在 1，fast 在 2。第一次循环后 slow 到 2，fast 到 4；第二次循环后 slow 到 3，fast 到 null，循环结束。此时 slow 停在 3，正好是正中间那个节点。

规律是这样的：偶数长度时，slow 停在左半段末尾；奇数长度时，slow 停在中间节点。这两种情况下，slow->next都恰好指向真正需要反转的那一小段链表的开头。如果你换成slow = head, fast = head的初始化方式，结果会偏移半个位置，不是不能解，但奇数长度时中间节点也会混进比较范围，各种奇偶分支会绕得你头大。所以我的习惯很固定：slow = head, fast = head->next，把边界情况压缩到最简。

提示：记住这个结论的关键在于快指针先多走了一步，相当于把起点整体向右平移了一个位置，最终让慢指针落在“左中点”附近。

2.2 迭代反转链表的三个指针怎么记

单链表的反转是另一块基础操作。我习惯用三个指针，一个指向已经反转好的部分的头（prev），一个指向当前正在处理的节点（curr），一个用来保存当前节点的下一个位置（next）。每一步做两件事：把当前节点的 next 箭头掉头指向上一个节点，然后把 prev 和 curr 整体往右移。

ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; // 先保存后继，防止断链 curr->next = prev; // 箭头掉头 prev = curr; // prev 右移 curr = next; // curr 右移 } return prev; }

很多新手第一次写会犯同一个错误：先把curr->next = prev做了，才想起来要保存后继，结果链表从当前位置往后的所有节点全部丢失。所以这里最重要的一个顺序就是next = curr->next必须放在最前面，任何一行赋值都不能在保存 next 之前修改 curr 的指向。

这里也用不到递归反转，因为递归反转的空间复杂度是 O(n)，和前面说的问题一模一样。迭代三指针看起来啰嗦，但空间恒定是 O(1)，这也是回文链表这道题能保持整体空间 O(1) 的关键原因之一。

2.3 为什么只反转后半段而不是前半段

有人会问，反转前半段行不行？理论上是行得通的，但实际写起来很别扭。如果反转前半段，你得额外处理两条链表从中间向两侧生长时的连接关系，原链表后半段起点还挂在某个节点后面，不把连接拆干净，比较过程中很容易互相干扰。

反过来看“反转后半段”的好处：原链表的前半段保持原顺序不动，后半段反转后天然变成一个从原链表尾节点开始的逆序链表。此时“从头节点开始的前半段”和“从反转后半段开始的链表”刚好形成头对尾的镜像关系，比较逻辑就退化成了最普通的逐节点比对。

换个角度看，判断回文本质上就是判断一个序列和它的逆序是否相等。后半段反转后，我们不需要真的去倒着遍历链表，因为倒着遍历的单链表根本做不到。把后半段就地反转，等于给单链表制造了一个“伪前驱指针”，让原本不可能的逆向访问变成可能，这就是整道题的核心思想。

3. 手写代码与逐行细节拆解

3.1 C++ 和 Python 标准解法直接抄作业版

思路确定后，代码其实就是三个小步骤的拼装。先找中点，再反转中点之后的部分，最后逐个比较。C++ 完整实现如下：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: bool isPalindrome(ListNode* head) { if (head == nullptr) return true; // 1. 快慢指针找中点 ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } // 2. 反转后半段 ListNode* secondHalf = reverseList(slow->next); // 3. 逐节点比较 ListNode* p1 = head; ListNode* p2 = secondHalf; while (p1 && p2) { if (p1->val != p2->val) return false; p1 = p1->next; p2 = p2->next; } return true; } ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } };

Python 版本结构完全一样，写法上更简练一些：

class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: if head is None: return True slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next second = self.reverse(slow.next) p1, p2 = head, second while p1 and p2: if p1.val != p2.val: return False p1, p2 = p1.next, p2.next return True def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]: prev = None curr = head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev

Java 的实现思路完全一致，只要把ListNode的构造和空指针判断套上 Java 语法即可，不需要额外讨论。

3.2 关键步骤的边界条件速查表

代码一共十几行，但每一处都有值得停下来想一想的边界。下面几个点是我实际写的时候反复核对过的。

第一个是空链表。head == nullptr时直接返回 true，因为空链表在定义上没有元素，按回文的约定俗成算作回文。这个用例在判题系统里出现得很频繁，漏掉就一定会错。

第二个是为什么secondHalf = reverseList(slow->next)而不是reverseList(head)。如果一不小心把整条链表反转了，那后面的比较逻辑完全失去意义，因为原链表的前半段顺序已经被破坏。这里必须明确：slow 停下的位置就是前半段的末尾，slow->next才是后半段的开头。

第三个是比较循环的终止条件。写成while (p1 && p2)而不是while (p1)，因为后半段反转后的长度要么等于前半段，要么比前半段少一个节点。在比较过程中，p2 一定比 p1 先走到空。如果循环条件只看 p1，一旦 p2 为空，下一轮循环再访问p2->val就会直接触发空指针异常。

第四个是值比较的位置。不要在 while 条件里写p1->val == p2->val，那样循环结束后你无法区分“是正常全部相等退出”还是“中间某一次不相等退出”，还得额外加条件判断，代码容易绕晕。正确的写法是把“不相等直接返回 false”放进循环体内部，循环正常走完就代表全部相等。

这张表建议你在写代码前自己动手推一遍，尤其是长度 3 和长度 5 的情况。推完会发现，奇数长度时正中间的节点根本不需要参与比较，因为它的对称节点就是它自己，p2 先走完时，p1 多出的那一个节点正好是中间节点。

3.3 时间与空间复杂度口算方法

时间复杂度这一项很好算。快慢指针找中点，本质上只遍历了大约一半的链表；反转后半段，又遍历了一半；逐节点比较，再遍历一半。三段加起来，每个节点最多被访问两次，整体是一个 O(n) 的线性过程，和链表长度严格成正比。

空间复杂度稍微需要解释一下。我们只创建了固定数量的指针变量：slow、fast、p1、p2，还有反转函数里的 prev、curr、next。无论链表多长，这些变量数量都不变，所以空间复杂度是 O(1)。这正好满足题目进阶要求。

有些人会把“反转后半段”误认为需要复制一份链表，其实是完全没有复制节点的，只是把节点之间的指针方向做了一次扭转，节点本身还是原来那些节点。理解了这一点，空间 O(1) 的结论就非常自然。

4. 新手排雷：常见错误与恢复链表原状

4.1 五个高频 bug 和对应排查思路

这道题代码不长，但指针类的 bug 隐蔽性都很强，编译能过，一跑就崩。我把见过的、自己踩过的高频坑集中列一下。

第一个是快慢指针循环条件写错。有人写while (fast->next)，在某些长度的链表上，fast 已经走到最后一个节点时，访问fast->next->next就会越过空指针。标准写法是while (fast && fast->next)，两个判空条件缺一不可。

第二个是反转函数里的保存顺序。三指针反转的核心是next = curr->next必须在curr->next = prev之前执行。顺序一错，后半段节点直接丢失，后面所有比较都是空中楼阁。

第三个是反转范围搞错。reverseList(slow->next)和reverseList(head)是完全两回事。如果写成后者，整条链表的顺序被反转，比较逻辑直接崩溃。排查方法很简单：打印slow->next指向的节点值，确认它确实是后半段开头。

第四个是循环终止条件写错。用while (p1)代替while (p1 && p2)，p2 为空后继续访问，空指针异常几乎是必然的。还有人在比较循环里写while (p1 != p2)，拿指针地址做比较而不是比较节点值，结果基本永远是 false。

第五个是忘了处理head == nullptr。这个用例在判题系统里很常见，漏掉就是空指针崩在第一步。

4.2 如何做到比较后链表保持原样

LeetCode 原题没有规定不能修改链表，所以直接反转后半段、比较完不管它，是能通过判题并且空间满足要求的。但面试场景里经常会被追问一句：“如果要求返回结果后链表保持原样，你怎么做？”

答案其实很简单：比较完之后，把后半段再反转回来，重新接到 slow->next 上。

ListNode* second = reverseList(slow->next); bool result = true; ListNode* p1 = head; ListNode* p2 = second; while (p1 && p2) { if (p1->val != p2->val) { result = false; break; } p1 = p1->next; p2 = p2->next; } slow->next = reverseList(second); return result;

这里有两点必须注意。第一，一定要先完成比较、拿到结果之后，再去恢复链表。如果先恢复再比较，后半段顺序已经被改回原状，比较无从谈起。第二，恢复操作reverseList(second)的入参是 second，也就是已经被反转后的后半段链表的头。对已经反转过的链表再做一次反转，得到的就是最初的顺序，这一步之后再把结果接回 slow->next，整条链表就完全恢复原样了。

这个扩展版本的时间复杂度仍然是 O(n)，只是常数上多了一次反转遍历；空间复杂度依然是 O(1)。在面试里主动写出“比较后还能恢复”的版本，通常是比较加分的，因为它展示了你对指针扭转的掌控力，而不只是背了一个模板。

4.3 一套可以直接自测的用例清单

刷题最怕的是代码在示例用例上通过，提交后却在隐藏用例上翻车。回文链表的测试用例我一般按下面的清单过一遍：

• 空链表[]：应返回 true
• 单节点[1]：应返回 true
• 两个节点[1, 2]：应返回 false
• 两个相同节点[1, 1]：应返回 true
• 奇数长度回文[1, 2, 3, 2, 1]：应返回 true
• 偶数长度回文[1, 2, 2, 1]：应返回 true
• 非回文[1, 2, 3, 1]：应返回 false
• 所有值相同[1, 1, 1, 1, 1]：应返回 true

前面两个用例最容易漏。空链表和单节点的返回值都是 true，很多新手第一反应是“空链表也算回文吗”，按判题系统的约定，算。所有值相同的用例也很容易让人误判，虽然它看起来没有结构上的对称感，但回文判断只关心值序列，值全部相同当然满足回文定义。

如果你是在本地调试，建议在反转函数执行前后分别打印链表内容，确认反转范围正确。指针类 bug 靠肉眼读代码常常看不出来，但把链表打印出来一对比，问题位置立刻暴露。

5. 从这题延伸出去的双指针套路

5.1 双指针还能解决哪些链表题目

回文链表只是链表双指针体系里的一环。快慢指针能解决的问题覆盖面很广，常见的至少还有这几类。

判断链表是否有环：一个每次走两步，一个每次走一步，如果两者能够相遇，说明链表中存在环。原理和这里找中点一样，利用速度差制造“追赶”效果。

寻找链表中点：很多排序、分治类题目都要先用快慢指针找到中点，才能把链表拆成前后两半。归并排序的链表版本尤其典型，先找中点再递归切分，最后合并。

删除链表倒数第 N 个节点：双指针先拉开 N 步距离，然后同时前进，当前面的指针到达末尾时，后面的指针正好停在待删除节点的前一个位置。

链表反转是一整个系列：反转整个链表、反转区间链表、K 个一组反转。这些题的核心操作都是三指针反转，只是在哪里停下、反转多少、反转之后如何拼接上有所变化。

所以回文链表这道题练熟之后，等于是把“找中点 + 反转链表 + 双指针比较”三个技能点打包带走。再遇到其他链表题，至少会有一个清晰的切入方向，而不是看到题就发懵。

5.2 我刷这题之后总结的两条心法

说点实际的个人体会。我最早做这题的时候，第一版就是转数组，5 分钟写完，一提交也被接受了，但那会儿并没有真正理解链表的操作感。后来有一次准备面试，被问到链表回文，我下意识又想写数组，对面直接问“能不能 O(1) 空间”，我才开始老老实实练反转链表。

练熟之后再回头做这道题，整个流程就变成了流水线：快慢指针找中点，反转后半段，逐节点比较。几乎不用动脑，手就直接跟着走。那段经历让我养成了一个习惯：链表相关的笔试面试题，先想双指针能不能套用；能套用的，就按“定位特殊位置、局部调整指针、恢复或者比较”这个思路拆。

最后还有一个实战小技巧值得分享。如果你在面试现场写这道题，不要一上来就闷头敲代码。先花十秒钟把思路讲清楚：先用快慢指针找到中点，再反转后半段，然后逐节点比较。写完代码后，主动用1-2-2-1和1-2-3-2-1这两个用例手动走一遍。这个动作花不了多少时间，但是能帮你在心里把每一步指针的位置过一遍，至少能拦下一半的指针类 bug。我试过几次，效果比回头检查代码明显得多。