企业官网建设流程全解析

LeetCode-Go 题解：234. Palindrome Linked List 回文链表判断的 O(1) 空间实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode-Go 仓库中 leetcode/0234.Palindrome-Linked-List 的官方题解为主体，系统讲解「判断单链表是否为回文链表」这一经典问题：从题目要求、边界条件出发，对比两种主流解法（辅助数组版与原地反转版），并结合仓库源码逐行拆解“快慢指针找中点 + 反转后半段 + 双指针比对”的 O(n) 时间、O(1) 空间实现，以及配套测试用例的构造方式。读完本文，你将能够独立推导并落地这道题及其变体（如 143. Reorder List）的进阶解法。

题目描述与示例

原题要求：给定一个单链表（singly linked list），判断它是否是一个回文链表。

示例 1：

Input: 1->2 Output: false

示例 2：

Input: 1->2->2->1 Output: true

进阶要求（Follow up）：能否在O(n) 时间复杂度与O(1) 空间复杂度内完成判断？

对于这道题，O(n) 时间比较容易满足；真正的难点在于O(1) 空间——它不允许使用与链表长度线性相关的额外存储（如数组、栈、哈希表），只能在常数个指针变量内完成。

题目大意与核心考点

判断一个链表是否是回文链表。要求时间复杂度 O(n)，空间复杂度 O(1)。

该题的核心考点可以拆解为三项基础链表操作：

1. 寻找链表中点——快慢指针法（快指针每次走两步，慢指针每次走一步）；
2. 反转链表区间——将中间结点到末尾的子链表原地反转；
3. 双指针顺序比对——从头结点与反转后的后半段头结点开始逐一比较。

这也是该题与 143. Reorder List 思路“完全一致”的原因：143 题在找到中点并反转后半段后做的是交叉拼接，而本题在同样步骤之后做的是对称比对。

解法一：辅助数组版（O(n) 空间）

仓库源码中的第一个实现 234. Palindrome Linked List.go 是最直观的思路：将链表的值全部读入一个切片，再用双指针从两端向中间比对。

// 解法一 func isPalindrome(head *ListNode) bool { slice := []int{} for head != nil { slice = append(slice, head.Val) head = head.Next } for i, j := 0, len(slice)-1; i < j; { if slice[i] != slice[j] { return false } i++ j-- } return true }

• 时间：O(n)，遍历链表一次装入数组，双指针比对 n/2 次；
• 空间：O(n)，需要一个与链表等长的[]int切片；
• 优点：逻辑极其简单，无需任何指针操作，且不会修改原链表结构；
• 缺点：不满足 Follow up 的 O(1) 空间要求。

边界条件：空链表（head == nil）与单结点链表在数组版中天然成立——空切片双循环不执行返回true，单元素切片首尾即同一元素返回true。

解法二：原地反转后半段（O(1) 空间）

仓库源码中的第二个实现 234. Palindrome Linked List.go 才是满足进阶要求的版本，注释明确说明“此题和 143 题 Reorder List 思路基本一致”。

// 解法二 // 此题和 143 题 Reorder List 思路基本一致 func isPalindrome1(head *ListNode) bool { if head == nil || head.Next == nil { return true } res := true // 寻找中间结点 p1 := head p2 := head for p2.Next != nil && p2.Next.Next != nil { p1 = p1.Next p2 = p2.Next.Next } // 反转链表后半部分 1->2->3->4->5->6 to 1->2->3->6->5->4 preMiddle := p1 preCurrent := p1.Next for preCurrent.Next != nil { current := preCurrent.Next preCurrent.Next = current.Next current.Next = preMiddle.Next preMiddle.Next = current } // 扫描表，判断是否是回文 p1 = head p2 = preMiddle.Next for p1 != preMiddle { if p1.Val == p2.Val { p1 = p1.Next p2 = p2.Next } else { res = false break } } if p1 == preMiddle { if p2 != nil && p1.Val != p2.Val { return false } } return res }

第一步：快慢指针寻找中间结点

p1 := head p2 := head for p2.Next != nil && p2.Next.Next != nil { p1 = p1.Next p2 = p2.Next.Next }

• p2（快指针）每次前进两步，p1（慢指针）每次前进一步；
• 循环结束后，p1落在链表中点：对于偶数长度链表，它位于左半段的最后一个结点（即“中点的前一个”）；对于奇数长度链表，它位于真正的中间结点；
• 循环条件p2.Next != nil && p2.Next.Next != nil保证了快指针不会越界，同时使p1停在左中结点，这一位置正是后续反转的“锚点”。

第二步：原地反转后半段链表

preMiddle := p1 // 后半段的虚拟头（前驱） preCurrent := p1.Next // 后半段当前的第一个结点 for preCurrent.Next != nil { current := preCurrent.Next preCurrent.Next = current.Next current.Next = preMiddle.Next preMiddle.Next = current }

这是典型的头插法反转区间操作：不断将preCurrent后面的结点摘下，插入到preMiddle之后。执行完毕后，链表从1->2->3->4->5->6变为1->2->3->6->5->4——后半段被原地逆序，且没有申请任何新结点，空间复杂度保持 O(1)。与 0143.Reorder-List 解法一中的反转代码完全同构，只是少了后续交叉拼接的循环。

第三步：双指针比对回文性

p1 = head p2 = preMiddle.Next for p1 != preMiddle { if p1.Val == p2.Val { p1 = p1.Next p2 = p2.Next } else { res = false break } } if p1 == preMiddle { if p2 != nil && p1.Val != p2.Val { return false } }

• p1从头结点出发，p2从反转后后半段的新头（即原链表尾）出发，逐个比对值；
• 主循环以p1 != preMiddle为终止条件，覆盖了左半段的全部结点；
• 循环后的收尾判断处理奇数长度链表的情况：当p1恰好走到中点preMiddle时，若p2尚未耗尽且与中点值不等，则直接判定非回文；否则返回res。

空间复杂度分析

整个解法只使用了p1、p2、preMiddle、preCurrent、current等常数个指针变量，没有使用与 n 相关的线性存储，因此满足 O(1) 空间复杂度要求；时间复杂度为 O(n)（找中点 n/2 + 反转 n/2 + 比对 n/2）。

需要留意的一点：该解法会就地修改原链表（后半段被反转）。如果题目环境要求链表后续继续使用，可在比对结束后再反转一次后半段以恢复原状。

测试用例：边界与奇偶全覆盖

仓库为本题配备了完整的表驱动测试 234. Palindrome Linked List_test.go，共 10 组用例，覆盖了回文判断的关键边界：

测试通过structures.Ints2List(p.one)将整数切片转换为链表后传入两个解法，并用工具函数L2ss校验链表转回切片后与原输入一致（防止解法破坏链表结构导致数据丢失），这与仓库 structures/ListNode.go 中Ints2List/List2Ints的设计一脉相承。

关联源码：共用 ListNode 结构与类型别名

两种解法的函数签名均为func isPalindrome(head *ListNode) bool，其中的ListNode并不是单独定义，而是通过类型别名复用仓库公共结构：

// ListNode define type ListNode = structures.ListNode

其底层定义在 structures/ListNode.go：

type ListNode struct { Val int Next *ListNode }

公共包还提供了Ints2List（切片转链表）、List2Ints（链表转切片，含 100 层深度环检测保护）等工具函数，使得各题解与测试可以以[]int为单位编写，大幅提升可读性与可维护性。

如何运行与验证

在仓库根目录执行单元测试即可验证本题两种解法及其测试用例：

go test ./leetcode/0234.Palindrome-Linked-List/ -v

若需连同全仓库一起跑覆盖率统计，可直接使用仓库自带的 gotest.sh 脚本（基于 Go 1.10+ 的多包-coverprofile特性，生成单一合法的覆盖率文件）：

bash gotest.sh

注意：仓库go.mod声明go 1.19并依赖本地模块（structures等通过replace指令指向相对路径），因此首次运行前建议在仓库根目录执行go mod tidy以拉齐依赖；上述命令均只需读取仓库源码即可运行，无需修改任何文件。

小结

• 数组版（isPalindrome）：实现直观、零指针操作，时间 O(n)、空间 O(n)，适合面试中先给出的“保底”方案；
• 原地版（isPalindrome1）：快慢指针找中点 + 头插法反转后半段 + 双指针比对，时间 O(n)、空间 O(1)，满足 Follow up 要求，且与 143 题 Reorder List 共享同一套核心操作，可一题打通两题；
• 测试覆盖：10 组用例覆盖空链表、单结点、奇偶长度、全等元素与各类非回文结构，配合公共ListNode工具函数，保证解法正确性与链表结构完整性。

掌握本题，等于同时掌握了「链表找中点」「链表区间反转」「链表双指针对称比对」三个高频基础技能，是攻克一系列链表进阶题（Reorder List、Reverse Nodes in k-Group 等）的基石。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go