企业官网建设流程全解析

1. 写在前面：为什么回文链表值得刷

力扣Hot100的题单我断断续续刷了三轮，如果让我挑一道最适合练链表基本功的题，我会毫不犹豫选第234题“回文链表”。这道题在力扣上标的是简单，但实际面试出现的频率一点也不低，而且它把链表最核心的几个操作全揉在了一起：遍历、找中点、反转、双指针。很多人一看题目觉得不就是判断回文嘛，结果自己动手写的时候，要么快慢指针的循环条件写错，要么反转完链表直接断掉，要么比较到一半发现空指针。这篇文章我结合自己的刷题记录，把回文链表的解法一层层拆开讲清楚，从最容易想到的数组法一路讲到空间O(1)的最优解，顺便把面试官可能会追问的问题也整理出来。正在刷力扣Hot100的同学可以把它当作一次链表基本功的自检，基础薄弱的开发者也能通过这道题把反转链表和快慢指针彻底弄明白。

1.1 一道看起来简单，其实很有深度的题

题目描述很短：给定一个单链表的头节点 head，判断它是不是回文链表。示例也很直观，1->2->2->1 返回 true，1->2 返回 false。字符串回文大家都会判断，两个指针一头一尾往中间走就行。可链表是单向的，尾指针没法直接往回走，这就让原本简单的问题多了一层思考空间。力扣在题目最后还加了一个进阶要求：能不能用 O(n) 时间复杂度和 O(1) 空间复杂度解决？这句话才是真正的考点。只要求判断回文，转成数组基本就完事了；但加上空间限制后，你必须想出“原地判断”的办法，于是快慢指针、反转链表这些基础技能就全被调动起来了。

1.2 这道题适合谁来刷

如果你是刚开始刷力扣Hot100的新手，我建议先不要直接看最优解，而是老老实实从数组法写起，跑通之后再尝试快慢指针反转法。如果你已经在准备面试，那这道题值得反复手写，尤其是“反转后半段并恢复原链表”这段逻辑，很多面试官会揪着细节追问。对于只想补基础的人来说，回文链表也是一道很好的综合训练题，它不像那些需要数学技巧的难题，只要链表基本功扎实，完全可以自己推导出来。刷透这道题之后，再去做重排链表、删除链表倒数第N个节点这类题，你会明显感觉到思路变顺了。

2. 题目拆解：回文链表到底在考什么

2.1 从回文串到回文链表：核心难点

回文的定义很简单：正着读和倒着读一样。在数组或者字符串里，判断回文通常用双指针，左边从0开始，右边从末尾开始，不断向中间靠拢，遇到不相等的字符就返回 false。这个过程最大的前提是“可以随机访问”——我想看最后一个元素，直接下标取到就行。链表不具备这个能力，它只有 next 指针，你只能从头节点开始，一个节点一个节点往下走。想拿到尾节点，要么遍历一遍记住位置，要么就得想别的办法。这就引出了这道题真正的核心矛盾：如何在单向遍历的限制下，实现“从两头到中间”的比较。理解了这一点，你就算看透了出题人的心思。

2.2 Hot100选这道题的逻辑

力扣Hot100收录的题目，并不全是那种让人挠头的难题，反而有很多“基础但综合”的题目。回文链表就是这样一道典型的筛选器。面试者如果只写出转数组的方法，说明基础合格，但距离“熟练”还有距离。能写出快慢指针加反转的 O(1) 空间解，说明他至少掌握了两项最重要的链表技能。要是还能主动恢复原链表，那基本可以确定这个人对指针操作有清晰的认识。所以 Hot100 选这道题，不是因为它难，而是因为它能高效地区分出“背过题解”和“真正理解链表”两类人。把这道题吃透，你收获的不仅仅是一道题的答案，而是一整套链表题的分析框架。

3. 从暴力到最优：三种解法怎么一步步想出来

3.1 最容易想到的办法：转数组双指针

第一次遇到这道题的时候，我脑子里冒出来的就是“把链表变成数组然后再判断”。这很自然，因为数组支持随机访问，判断回文就回到了我们熟悉的双指针套路。实现也很简单：先遍历链表，把所有节点的值存进一个 ArrayList，然后用 left 和 right 两个下标从两端往中间比较。代码大概长这样：

public boolean isPalindrome(ListNode head) { List<Integer> vals = new ArrayList<>(); ListNode cur = head; while (cur != null) { vals.add(cur.val); cur = cur.next; } int left = 0; int right = vals.size() - 1; while (left < right) { if (!vals.get(left).equals(vals.get(right))) { return false; } left++; right--; } return true; }

这段代码时间复杂度是 O(n)，空间复杂度也是 O(n)，因为额外存了一份链表的值。好处是思路清晰、不容易出错，作为面试第一步抛出来完全没问题。但我后来面试别人时发现，不少候选人会在这里犯一个隐蔽的错误：比较两个 Integer 的时候用了==。如果链表长度比较长，节点值超出Integer缓存范围，==比较的是引用而不是值，结果就会莫名其妙出错。所以这里一定要用equals。这个解法最大的短板就是空间，面试官只要追问“能不能不用额外空间”，你就得拿出下一招。

3.2 用递归让系统栈帮忙逆序

第二种思路是利用递归回溯来实现链表的逆序访问。递归函数会一直向下走到链表的尾节点，然后在回溯的过程中逐层返回，这个行为天然就相当于“从后往前”遍历。我们只需要额外维护一个指向头部的指针，在每次回溯时比较当前节点和头部指针指向的节点，就能完成回文判断。代码可以写成这样：

private ListNode front; public boolean isPalindrome(ListNode head) { front = head; return recurse(head); } private boolean recurse(ListNode node) { if (node != null) { if (!recurse(node.next)) { return false; } if (front.val != node.val) { return false; } front = front.next; } return true; }

这个解法时间上依然是 O(n)，但空间上是 O(n) 的递归栈空间。它的好处是代码非常短，而且能锻炼递归思维，但我不建议在面试中把它作为主答案。原因有两个：一是链表很长时递归深度过大，可能出现栈溢出；二是递归本身就比迭代难调试，一旦逻辑出问题，你很难快速定位是哪一层比较出了问题。所以它更适合当作一个“我知道还有这种思路”的补充答案，而不是最终解法。

3.3 最优解：快慢指针加反转后半段

最优解的核心思路是：既然链表不能直接从后往前遍历，那我们就手动把后半段链表反转，让后半段的头变成“尾节点”，这样就人为造出了一条从尾部向前走的路径。整个流程分三步：

1. 用快慢指针找到前半段的末尾节点。
2. 把后半段链表反转。
3. 同时遍历前半段和反转后的后半段，逐节点比较。

为什么这样能省空间？因为我们没有用额外的容器，只是把链表本身的 next 指针做了一些调整。空间复杂度降到了 O(1)。这里有一个关键点需要注意：反转后半段会改变原链表的结构。如果面试官要求不能修改原链表，那就在比较完成之后再把后半段反转回来。这正是这道题最精彩的地方。很多人能想到快慢指针找中点，也能想到反转链表，但把两者组合起来之后，还能意识到“要恢复原链表”的人就少了很多。接下来我们进入完整实现。

4. 核心实现：完整代码与关键步骤拆解

4.1 快慢指针怎么找前半段末尾

先看第一步，快慢指针找位置。初始化时 slow 和 fast 都指向 head，slow 每次走一步，fast 每次走两步。循环条件要写成while (fast.next != null && fast.next.next != null)，而不是常见的while (fast != null && fast.next != null)。区别在于循环结束后 slow 落在哪里。

用奇数长度链表 1->2->3->2->1 举例：slow 最终会落在节点3，也就是正中间，同时也是前半段的最后一个节点。用偶数长度链表 1->2->2->1 举例：slow 最终会落在第二个节点2，它是前半段的末尾。这个位置非常关键，因为我们要拿slow.next作为后半段的起始节点。如果循环条件写错，slow 落在正中间而不是前半段末尾，后面反转后半段时就会多包含一个节点，比较逻辑就会出错。我建议你在纸上把这个过程画出来，比背结论要牢靠得多。

4.2 反转链表怎么保证不断链

第二步是反转后半段。反转链表本身也是力扣里的一道经典题，回文链表相当于把它嵌套进来了。迭代反转的核心逻辑是维护三个指针：prev、cur、next。每次循环先保存 cur.next，再把 cur.next 指向前一个节点，然后整体平移。代码是这样：

private ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }

这里最容易犯的错误就是忘记先保存 next。一旦你先执行了cur.next = prev，原来的下一个节点就找不到了，链表会从中间断开，后面的节点全部丢失。这种错误在本地跑的时候通常会表现为死循环或者结果错乱。反转结束后，原后半段的尾节点变成了新头，也就是我们接下来要比较的“右侧起始点”。

4.3 比较阶段与链表恢复

第三步是比较。左侧指针从原链表 head 开始，右侧指针从反转后的后半段头开始。这里我强烈建议循环条件写成while (p2 != null)，而不是while (p1 != null)。因为反转后的后半段长度小于等于前半段，当 p2 走完时，所有需要比较的对称节点都已经比较过了。如果写成 p1 != null，奇数长度链表会让 p1 多走一个节点，此时 p2 已经是 null，再访问 p2.val 就会空指针异常。

比较完成之后，如果你想保持原链表结构不变，就再调用一次 reverse，把后半段恢复原状，然后接回 slow.next。完整的可运行代码如下：

class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode secondHead = slow.next; ListNode reversedHead = reverse(secondHead); ListNode p1 = head; ListNode p2 = reversedHead; boolean result = true; while (p2 != null) { if (p1.val != p2.val) { result = false; break; } p1 = p1.next; p2 = p2.next; } slow.next = reverse(reversedHead); return result; } private ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }

关于恢复那行，我多说一句：reversedHead是反转后后半段的头，也就是原链表的尾节点。对它再做一次 reverse，得到的就是原后半段的正常顺序，再赋给slow.next，整个链表就恢复了原样。很多人在这一步会犹豫，担心把原来的链表搞乱。你只需要记住，reverse 函数是幂等的，反转两次等于回到原点。

5. 复杂度、边界与调试心得

5.1 时间和空间复杂度一目了然

最优解的时间复杂度依然是 O(n)。可能有人会纠结：找中点 O(n/2)，反转 O(n/2)，比较 O(n/2)，加起来不是 1.5n 吗？算法分析里常数系数不参与复杂度表示，所以直接说 O(n) 没问题。空间复杂度则只有若干个指针变量，和链表长度无关，所以是 O(1)。这也是这道题进阶要求里最核心的指标。三种解法对比下来，数组法时间 O(n) 空间 O(n)，递归法时间 O(n) 空间 O(n)，最优解时间 O(n) 空间 O(1)。在时间量级相同的情况下，空间优势就成了面试的决胜点。

5.2 特殊链表形态测试用例表

我刷题时习惯在本地备一组边界用例，这道题我常测的有这些：

其中最容易出错的是长度 2 的情况。此时fast.next存在，但fast.next.next是 null，while 循环一次都不执行，slow 停在 head，后半段就是 head.next，反转后比较，逻辑完全正确。这个用例能帮你确认找中点循环的边界条件写对了。

5.3 我刷题时踩过的几个坑

第一个坑是快慢指针的循环条件。我早期一直写while (fast != null && fast.next != null)，结果奇数长度时 slow 会落在正中间，后半段头是 slow.next，这样中间节点被排除在比较范围之外。虽然中间节点本身不需要比较，但接下来的比较循环条件如果不调整，特别容易出问题。后来我统一改成fast.next.next的写法，让 slow 落在前半段末尾，思路就顺了。

第二个坑是反转函数里没有先保存 next。我踩过一次，反转后半段的时候链表直接断成两截，程序跑起来就像链表出现环一样，最后不得不重新画图才找到原因。从那以后我每次写反转，第一反应一定是先把 next 存下来。

第三个坑是比较循环条件写错。最开始我用while (p1 != null && p2 != null)，虽然不会空指针，但在奇数长度时 p1 会多走一步，逻辑上不干净。后来改成只判断 p2，代码简洁很多。调试链表题，我习惯在关键节点后打印整个链表，写一个简单的 printList 辅助函数，方便快速确认每一步的指针状态。链表题光靠脑内推演很容易错，纸上画图或者加日志，是最高效的调试方式。

6. 从刷题到面试：这道题的通用方法论

6.1 面试官的典型追问

面试官看到你能写出最优解，通常会继续问几个问题来确认你是真会还是背题。第一个问题大概率是“能不能不用额外空间”，这时候你已经用快慢指针加反转回答了。第二个问题会是“你这样做会修改原链表吗”，你要能想到在比较结束后把后半段反转回去。第三个问题可能会是“能不能一次遍历就完成”，严格说，完整的一次遍历且空间 O(1) 很难做到，常见做法是在找中点的过程中边移动边反转前半段，但整体仍然需要二次比较，所以不用纠结这种措辞问题，把思路讲清楚就行。

另外面试官还可能扩展问一些变体：如果链表存的是字符串而不是整数，怎么比较？答案很简单，用 equals 而不是 ==。如果链表是双向链表，判断回文是不是更简单？确实是，因为有前驱指针，直接从两端往中间走即可。如果链表有环呢？那就得先判断是否有环，因为环存在时“回文”本身就失去了意义。

6.2 链表题通用的几个套路

链表题刷多了会发现，底层方法就那么几个：快慢指针、反转链表、哑节点、双指针。回文链表无非是把其中两个组合到一起。遇到新题时，先思考能不能拆解成这些基础操作。比如“重排链表”需要先找中点，再反转后半段，然后交叉合并，和回文链表的前两步几乎一模一样。“删除链表倒数第N个节点”用快慢指针，先让 fast 走 N 步，再让两个指针同步走。“环形链表”也是快慢指针，检测是否相遇。把这些基础工具练熟，很多题都是套模板的事。

实际面试时还有一个通用技巧：在写代码之前，先在白板上画一个三节点的链表，手动模拟一遍算法流程。这样既能帮自己理清思路，也能让面试官看到你不是在硬背答案。代码写完后，再用一两个特殊用例走一遍，比如偶数长度、只有一个节点，基本就能避免大部分低级错误。

6.3 回文链表思维在工程里的延伸

有人觉得刷算法题和日常工作关系不大，但链表的这些基础操作在真实系统里确实存在。比如 Java 的 LinkedList 底层是双向链表，浏览器历史记录、编辑器撤销操作，本质都是在线性结构里做逆序访问。再比如 LRU 缓存淘汰策略，需要同时用哈希表和双向链表，链表中节点的删除和移动，靠的就是对 next 和 prev 指针的精确控制。回文链表这种“在单向访问结构里做双向思考”的能力，是一种可以迁移到其他地方的分析方式。遇到类似场景，比如协议报文的对称性检查、日志回放时的校验，你自然就会想到用双指针或者栈去处理。

这道题我前后刷过好几遍，每一遍都有新体会。最开始我也只会转数组，后来才慢慢理解快慢指针加反转的妙处。如果你正在准备面试，我建议把恢复链表的那段单独拿出来练到闭着眼睛都能写，因为面试官真的会追问。也可以自己构造几个特殊用例，把所有边界条件全跑一遍。等你能把“为什么循环条件是 fast.next.next”“为什么比较循环要看 p2”这两句话解释清楚，这道题才算真正吃透了。最后再分享一个小技巧：链表题写完后，在纸上画一个三节点和四节点的用例，手动走一遍指针变化，比任何调试工具都有效。