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

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判断它是否是一个回文链表。示例 1Input: 1-2 Output: false示例 2Input: 1-2-2-1 Output: true进阶要求Follow up能否在O(n) 时间复杂度与O(1) 空间复杂度内完成判断对于这道题O(n) 时间比较容易满足真正的难点在于O(1) 空间——它不允许使用与链表长度线性相关的额外存储如数组、栈、哈希表只能在常数个指针变量内完成。题目大意与核心考点判断一个链表是否是回文链表。要求时间复杂度 O(n)空间复杂度 O(1)。该题的核心考点可以拆解为三项基础链表操作寻找链表中点——快慢指针法快指针每次走两步慢指针每次走一步反转链表区间——将中间结点到末尾的子链表原地反转双指针顺序比对——从头结点与反转后的后半段头结点开始逐一比较。这也是该题与 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 组用例覆盖了回文判断的关键边界输入链表期望结果覆盖点[]int{1, 1, 2, 2, 3, 4, 4, 4}false非回文、偶数长度[]int{1, 1, 1, 1, 1, 1}true全等元素回文[]int{1, 2, 2, 1, 3}false奇数长度、尾部破坏回文[]int{1}true单结点链表[]int{}true空链表[]int{1, 2, 2, 2, 2, 1}true偶数长度回文[]int{1, 2, 2, 3, 3, 3, 3, 2, 2, 1}true较长回文[]int{1, 2}false两个结点非回文[]int{1, 0, 1}true奇数长度回文[]int{1, 1, 2, 1}false前半回文后半非回文测试通过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.gotype 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考