algorithm-base 动画学算法：LeetCode 234 回文链表详解——巧用数组法与快慢指针翻转法的完整实战

文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载导读本文是 algorithm-base 仓库「链表篇」系列的技术指南围绕 LeetCode 234「回文链表」展开先给出思路直白、代码简单的数组 双指针解法再进阶到空间复杂度 O(1) 的快慢指针找中点 后半反转 双指针比较解法并完整提供 Java、C、JavaScript、Python、Swift、Go 六种语言的实现。读完本文你不仅能独立 AC 这道高频面试题还能把「找中间节点」「反转链表」两个链表基本功迁移到其他题目中。题目描述与示例原题234. 回文链表请判断一个链表是否为回文链表。示例 1输入: 1-2 输出: false示例 2输入: 1-2-2-1 输出: true题目理解起来很简单判断链表从头读和从尾读是否一致。如果给的是一个字符串或者数组这个问题几乎不需要思考——因为数组支持 O(1) 时间复杂度的随机访问可以用两个指针一头一尾向中间靠拢。但本题的难点恰恰在于题目给的是单链表。为什么链表判回文比数组困难单链表有两个固有特性让回文判断变难查询时间复杂度高链表查询某个下标元素的时间复杂度为 O(n)无法像数组那样按下标 O(1) 随机访问指针只能单向移动单链表的每个节点只保存指向后继节点的引用next指针只能后移不能前移天然不支持从尾部往前读。所以我们需要借助额外数据结构数组或者改变链表本身反转才能实现从两端往中间比较的效果。下面分别展开这两种思路。解法一巧用数组法辅助数组 双指针解题思路思路非常朴素分两步拷贝遍历链表把所有节点的值按顺序存入一个动态数组双指针扫描back指向数组头部pro指向数组尾部同时向中间靠拢逐一比较两个指针指向的值是否相等。只要有一对不相等就说明不是回文直接返回false全部相等则返回true。该方法很容易理解代码实现也比较简单且对链表本身没有任何副作用。复杂度分析时间复杂度O(n)。一次遍历拷贝链表 双指针扫描约 n/2 次整体仍是线性空间复杂度O(n)。需要一个与链表等长的辅助数组。由于使用了辅助数组该方法可以直接通过AC但面试中常常会继续追问能否把空间复杂度降到 O(1)各语言实现注意拷贝时需要用到动态数组Java 的ArrayList、C 的vector、Python 的list等因为我们预先不知道链表长度。链表节点的基础结构可参考仓库中的 Leetcode常用类和函数.md如 Java 中ListNode list new ListNode(0)的初始化方式。Java Codeclass Solution { public boolean isPalindrome(ListNode head) { //这里需要用动态数组因为我们不知道链表的长度 ListInteger arr new ArrayListInteger(); ListNode copynode head; //将链表的值复制到数组中 while (copynode ! null) { arr.add(copynode.val); copynode copynode.next; } //双指针遍历数组 int back 0; int pro arr.size() - 1; while (back pro) { //判断两个指针的值是否相等 if (!arr.get(pro).equals(arr.get(back))) { return false; } //移动指针 back; pro--; } return true; } }C Codeclass Solution { public: bool isPalindrome(ListNode* head) { //这里需要用动态数组因为我们不知道链表的长度 vectorint arr; ListNode* copynode head; //将链表的值复制到数组中 while (copynode) { arr.push_back(copynode-val); copynode copynode-next; } //双指针遍历数组 int back 0; int pro arr.size() - 1; while (back pro) { //判断两个指针的值是否相等 if (arr[back] ! arr[pro]) { return false; } //移动指针 back; pro--; } return true; } };JS Codevar isPalindrome function (head) { let arr []; let copynode head; //将链表的值复制到数组中 while (copynode) { arr.push(copynode.val); copynode copynode.next; } //双指针遍历数组 let back 0; let pro arr.length - 1; while (back pro) { //判断两个指针的值是否相等 if (arr[back] ! arr[pro]) { return false; } //移动指针 back 1; pro - 1; } return true; };Python Codeclass Solution: def isPalindrome(self, head: ListNode) - bool: arr [] copynode head # 将链表的值复制到数组中 while copynode is not None: arr.append(copynode.val) copynode copynode.next # 双指针遍历数组 back 0 pro len(arr) - 1 while back pro: # 判断两个指针的值是否相等 if arr[back] ! arr[pro]: return False # 移动指针 back 1 pro - 1 return TrueSwift Codeclass Solution { func isPalindrome(_ head: ListNode?) - Bool { // 这里需要用动态数组因为我们不知道链表的长度 var arr:[Int?] [] var copynode head // 将链表的值复制到数组中 while copynode ! nil { arr.append(copynode?.val) copynode copynode?.next } // 双指针遍历数组 var back 0, pro arr.count - 1 while back pro { // 判断两个指针的值是否相等 if arr[pro] ! arr[back] { return false } // 移动指针 back 1 pro - 1 } return true } }Go Codefunc isPalindrome(head *ListNode) bool { // 将节点中的值按顺序放在arr中。 arr : []int{} node : head for node ! nil { arr append(arr, node.Val) node node.Next } // 双指针判断是否为回文 l, r : 0, len(arr) - 1 for l r { if arr[l] ! arr[r] { return false } l r-- } return true }一个小细节Java 中为什么用equals而不是Java 版比较时写的是!arr.get(pro).equals(arr.get(back))而不是arr.get(pro) ! arr.get(back)。原因是ArrayListInteger中存放的是包装类型Integer比较的是引用地址虽然对于 -128~127 区间内的整数 JVM 有缓存IntegerCache通常也能比较通过但超出该区间的值就会失效。使用equals比较的是数值本身更为稳妥。解法二双指针翻转链表法O(1) 额外空间总体思路三步走既然单链表不能从后往前遍历我们干脆手动把后半部分调个头让后半部分的头变成尾部这样就能用两个头指针从前半和后半同时向后走逐一比较。整个方案分为三步找中点用快慢指针找到链表的中间节点作为后半部分的起点反转后半原地反转中间节点之后的链表逐对比较 还原用两个指针分别遍历前半部分和后半部分比较值是否相等比较结束后把后半部分再次反转恢复原链表结构。其中第 1、2 步正是仓库「链表篇」中两个经典题目的直接应用找中间节点对应仓库文档 面试题 02.03. 链表中间节点.md反转链表对应仓库文档 leetcode206反转链表.md。步骤一快慢指针寻找中间节点快慢指针的思路是让fast一次走两步、slow一次走一步。当fast走到链表末尾时slow恰好停留在链表中间。在仓库文档 面试题 02.03. 链表中间节点.mdLeetCode 876中标准写法是while (fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; }注意本题与 876 题的关键差异876 题要求如果有两个中间结点则返回第二个中间结点而本题的searchmidnode循环条件是while (fast.next ! null fast.next.next ! null) { fast fast.next.next; slow slow.next; }两者循环条件不同导致返回的中点不同当链表长度为奇数如 5 个节点时两种写法返回的都是正中间那一个节点无差异当链表长度为偶数如 6 个节点时876 题返回第 4 个节点第二个中间节点而本题的写法返回第 3 个节点第一个中间节点。为什么本题要返回第一个中间节点因为我们要反转的是midnode.next之后的后半部分。以1-2-3-4为例若midnode是节点 2第一个中间节点则后半部分是3-4反转后与前半1-2逐一比较正好完成回文校验若误取了第二个中间节点节点 3反转4一个节点比较时前半会多出一个节点逻辑就错了。这正是细节多的地方。步骤二原地反转后半部分链表反转链表是另一道高频面试题仓库文档 leetcode206反转链表.md 给出了迭代三指针的完整推导low指向已反转部分的头初始为nulltemp记住当前节点pro向前移动把temp.next指向low再让low前移如此循环直到链表反转完毕。本题中直接复用该思路即可public ListNode reverse (ListNode slow) { ListNode low null; ListNode temp null; while (slow ! null) { temp slow.next; slow.next low; low slow; slow temp; } return low; }需要强调的一点是这里传入的是midnode.next而不是midnode本身。因为我们找到的是整个链表的中点要反转的是它之后的后半部分中点之前的链表要保持原样作为前半部分用于后续比较。步骤三双指针比较并记得还原链表反转完成后用p1指向链表头p2指向反转后的后半部分头两个指针同步前进并比较val。由于后半部分无论奇数长度还是偶数长度都不会比前半部分更长所以循环条件以p2 ! null为准即可。最容易忽略的细节是还原链表我们只是判断是否为回文不可以破坏输入链表的原始结构。因此无论比较结果是true还是false返回前都要把后半部分再反转一次接回midnode.next恢复原链表。midnode.next reverse(backhalf); return true;注意在提前返回 false的分支里同样需要先还原再返回if (p1.val ! p2.val) { //若要还原记得这里也要reverse midnode.next reverse(backhalf); return false; }虽然不还原也能通过 OJAC但面试时如果题目有不得修改原链表的附加要求漏掉这一步就会扣分。从源码结构看仓库中六种语言的实现都保留了返回前还原这一步说明这是该题解刻意强调的规范。各语言实现Java Codeclass Solution { public boolean isPalindrome(ListNode head) { if (headnull || head.nextnull) { return true; } //找到中间节点也就是翻转的头节点,这个在昨天的题目中讲到 //但是今天和昨天有一些不一样的地方就是如果有两个中间节点返回第一个昨天的题目是第二个 ListNode midnode searchmidnode(head); //原地翻转链表需要两个辅助指针。这个也是面试题目大家可以做一下 //这里我们用的是midnode.next需要注意因为我们找到的是中点但是我们翻转的是后半部分 ListNode backhalf reverse(midnode.next); //遍历两部分链表判断值是否相等 ListNode p1 head; ListNode p2 backhalf; while (p2 ! null) { if (p1.val ! p2.val) { //若要还原记得这里也要reverse midnode.next reverse(backhalf); return false; } p1 p1.next; p2 p2.next; } //还原链表并返回结果这一步是需要注意的我们不可以破坏初始结构我们只是判断是否为回文 //当然如果没有这一步也是可以AC但是面试的时候题目要求可能会有这一条。 midnode.next reverse(backhalf); return true; } //找到中点 public ListNode searchmidnode (ListNode head) { ListNode fast head; ListNode slow head; while (fast.next ! null fast.next.next ! null) { fast fast.next.next; slow slow.next; } return slow; } //翻转链表 public ListNode reverse (ListNode slow) { ListNode low null; ListNode temp null; while (slow ! null) { temp slow.next; slow.next low; low slow; slow temp; } return low; } }C Codeclass Solution { public: bool isPalindrome(ListNode* head) { if (head nullptr || head-next nullptr) { return true; } //找到中间节点也就是翻转的头节点这个在昨天的题目中讲到 //但是今天和昨天有一些不一样的地方就是如果有两个中间节点返回第一个昨天的题目是第二个 ListNode * midnode searchmidnode(head); //原地翻转链表需要两个辅助指针。这个也是面试题目大家可以做一下 //这里我们用的是midnode-next需要注意因为我们找到的是中点但是我们翻转的是后半部分 ListNode * backhalf reverse(midnode-next); //遍历两部分链表判断值是否相等 ListNode * p1 head; ListNode * p2 backhalf; while (p2 ! nullptr) { if (p1-val ! p2-val) { //若要还原记得这里也要reverse midnode-next reverse(backhalf); return false; } p1 p1-next; p2 p2-next; } //还原链表并返回结果这一步是需要注意的我们不可以破坏初始结构我们只是判断是否为回文 //当然如果没有这一步也是可以AC但是面试的时候题目要求可能会有这一条。 midnode-next reverse(backhalf); return true; } //找到中间的部分 ListNode * searchmidnode (ListNode * head) { ListNode * fast head; ListNode * slow head; while (fast-next ! nullptr fast-next-next ! nullptr) { fast fast-next-next; slow slow-next; } return slow; } //翻转链表 ListNode * reverse (ListNode * slow) { ListNode * low nullptr; ListNode * temp nullptr; while (slow ! nullptr) { temp slow-next; slow-next low; low slow; slow temp; } return low; } };JS Codevar isPalindrome function (head) { if (head null || head.next null) { return true; } //找到中间节点也就是翻转的头节点这个在昨天的题目中讲到 //但是今天和昨天有一些不一样的地方就是如果有两个中间节点返回第一个昨天的题目是第二个 let midnode searchmidnode(head); //原地翻转链表需要两个辅助指针。这个也是面试题目大家可以做一下 //这里我们用的是midnode.next需要注意因为我们找到的是中点但是我们翻转的是后半部分 let backhalf reverse(midnode.next); //遍历两部分链表判断值是否相等 let p1 head; let p2 backhalf; while (p2 ! null) { if (p1.val ! p2.val) { //若要还原记得这里也要reverse midnode.next reverse(backhalf); return false; } p1 p1.next; p2 p2.next; } //还原链表并返回结果这一步是需要注意的我们不可以破坏初始结构我们只是判断是否为回文 //当然如果没有这一步也是可以AC但是面试的时候题目要求可能会有这一条。 midnode.next reverse(backhalf); return true; }; //找到中点 var searchmidnode function (head) { let fast head; let slow head; while (fast.next ! null fast.next.next ! null) { fast fast.next.next; slow slow.next; } return slow; }; //翻转链表 var reverse function (slow) { let low null; let temp null; while (slow ! null) { temp slow.next; slow.next low; low slow; slow temp; } return low; };Python Codeclass Solution: def isPalindrome(self, head: ListNode) - bool: if head is None or head.next is None: return True # 找到中间节点也就是翻转的头节点这个在昨天的题目中讲到 # 但是今天和昨天有一些不一样的地方就是如果有两个中间节点返回第一个昨天的题目是第二个 midnode self.searchmidnode(head) # 原地翻转链表需要两个辅助指针。这个也是面试题目大家可以做一下 # 这里我们用的是midnode.next需要注意因为我们找到的是中点但是我们翻转的是后半部分 backhalf self.reverse(midnode.next) # 遍历两部分链表判断值是否相等 p1 head p2 backhalf while p2 is not None: if p1.val ! p2.val: # 若要还原记得这里也要reverse midnode.next self.reverse(backhalf) return False p1 p1.next p2 p2.next # 还原链表并返回结果这一步是需要注意的我们不可以破坏初始结构我们只是判断是否为回文 # 当然如果没有这一步也是可以AC但是面试的时候题目要求可能会有这一条。 midnode.next self.reverse(backhalf) return True # 找到中点 def searchmidnode(self, head): fast head slow head while fast.next is not None and fast.next.next is not None: fast fast.next.next slow slow.next return slow # 翻转链表 def reverse(self, slow): low None temp None while slow is not None: temp slow.next slow.next low low slow slow temp return lowSwift Codeclass Solution { func isPalindrome(_ head: ListNode?) - Bool { if head nil || head?.next nil { return true } //找到中间节点也就是翻转的头节点,这个在昨天的题目中讲到 //但是今天和昨天有一些不一样的地方就是如果有两个中间节点返回第一个昨天的题目是第二个 var midnode searchmidnode(head) //原地翻转链表需要两个辅助指针。这个也是面试题目大家可以做一下 //这里我们用的是midnode.next需要注意因为我们找到的是中点但是我们翻转的是后半部分 var backhalf reverse(midnode?.next); //遍历两部分链表判断值是否相等 var p1 head var p2 backhalf while p2 ! nil { if p1?.val ! p2?.val { midnode?.next reverse(backhalf) return false } p1 p1?.next p2 p2?.next } //还原链表并返回结果这一步是需要注意的我们不可以破坏初始结构我们只是判断是否为回文 //当然如果没有这一步也是可以AC但是面试的时候题目要求可能会有这一条。 midnode?.next reverse(backhalf) return true } //找到中点 func searchmidnode(_ head: ListNode?) - ListNode? { var fast head, slow head while fast?.next ! nil fast?.next?.next ! nil { fast fast?.next?.next slow slow?.next } return slow } //翻转链表 func reverse(_ slow: ListNode?) - ListNode? { var slow slow var low: ListNode? var temp: ListNode? while slow ! nil { temp slow?.next slow?.next low low slow slow temp } return low } }Go Codefunc isPalindrome(head *ListNode) bool { if head nil || head.Next nil { return true } midNode : searchMidNode(head) backHalf : reverse(midNode.Next) // 判断左右两边是否一样回文 p1, p2 : head, backHalf for p2 ! nil { if p1.Val ! p2.Val { midNode.Next reverse(backHalf) return false } p1 p1.Next p2 p2.Next } // 不破坏原来的数据 midNode.Next reverse(backHalf) return true } // searchMidNode 求中间的节点 func searchMidNode(head *ListNode) *ListNode { fast, slow : head, head for fast.Next ! nil fast.Next.Next ! nil { fast fast.Next.Next slow slow.Next } return slow } // reverse 反转链表 func reverse(node *ListNode) *ListNode { var pre *ListNode for node ! nil { nxt : node.Next node.Next pre pre node node nxt } return pre }复杂度分析时间复杂度O(n)。找中点 O(n/2)、反转后半 O(n/2)、双指针比较 O(n/2)、还原反转 O(n/2)整体仍是线性空间复杂度O(1)。全程只使用了若干个指针变量没有额外数据结构这是相比数组法最核心的改进。两种解法对比维度解法一巧用数组法解法二双指针翻转法核心思想链表转数组 双指针快慢指针找中点 反转后半 双指针比较时间复杂度O(n)O(n)空间复杂度O(n)辅助数组O(1)仅指针变量是否修改链表否比较后还原不破坏原结构实现难度简单适合秒杀中等需掌握两个子问题面试加分点思路直观空间优化 链表基本功综合运用边界情况与易错点总结综合两种解法建议在写代码前先想清楚下面这些边界情况空链表与单节点链表head null或head.next null时直接返回true空链表和单个节点天然是回文偶数长度链表中点的选择本题searchmidnode返回第一个中间节点循环条件fast.next ! null fast.next.next ! null与 LeetCode 876「返回第二个中间节点」不同反转的是midnode.next之后的部分比较循环的终止条件后半部分一定不比前半部分长用p2 ! null作为循环条件即可不会越界务必还原链表true/false两个返回路径都要把backhalf再反转一次接回midnode.next数组法中 Java 的equalsInteger包装类型比较数值应使用equals避免大整数下引用比较的坑。延伸阅读仓库链表篇相关题目本题是链表基本功的集大成者它用到的两个子问题在 algorithm-base 仓库中都有独立文档建议按顺序阅读面试题 02.03. 链表中间节点.md快慢指针找中点的完整推导LeetCode 876leetcode206反转链表.md迭代与递归两种反转写法leetcode92反转链表2.md部分区间反转反转思路的进阶应用剑指offer22倒数第k个节点.md一前一后双指针的另一种经典形态Leetcode常用类和函数.md链表节点ListNode及常用集合类速查更多链表题目索引见仓库 README.md 的「链表篇」章节。总结回文链表这道题从数组 双指针到快慢指针 反转后半本质上是把链表问题拆解为仓库中两个经典子问题找中点、反转链表的组合应用。建议读者先独立写出数组法确保思路正确、边界完备再实现翻转法重点体会中点选择偶数长度取第一个中点与返回前还原链表这两个细节最后尝试在不看答案的情况下把searchmidnode与reverse抽成独立函数并复用到其他题目中。掌握这道题你就同时拿下了链表题里最高频的三个考点快慢指针、链表反转、以及不破坏输入结构的工程意识。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐LeetCode 234 回文链表Palindrome Linked List全解法详解数组、递归、栈与快慢指针反转LeetCode 234 回文链表Palindrome Linked List全解法详解数组、递归、栈与快慢指针反转 回文链表LeetCode 234示例工程教程Label Studio 前端LSF初始化机制深度解析configureStore、initializeStore 与单标注选中策略Label Studio 前端LSF初始化机制深度解析configureStore、initializeStore 与单标注选中策略 本篇围绕 Label文档教程知识库LeetCode 876 链表的中间结点快慢双指针解法详解LeetCode-Book 实战解析LeetCode 876 链表的中间结点快慢双指针解法详解LeetCode Book 实战解析 导读 本文以 LeetCode Book 仓库中 876.示例工程上一篇Web-Dev-For-Beginners 浏览器扩展课第 3 讲背景任务、消息传递与性能剖析实战下一篇3步搞定用Python将复杂Word文档转成结构化JSON创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考