LeetCode 234.回文链表 详细技术解析（含O(n)时间O(1)空间优化）

LeetCode 234.回文链表 详细技术解析含O(n)时间O(1)空间优化本文针对LeetCode 234.回文链表问题从题目分析、基础解法、进阶优化三个维度进行详细技术拆解结合代码实现、示例验证及复杂度分析帮助开发者彻底掌握该题的解题思路同时适配题目提示要求重点讲解O(n)时间复杂度、O(1)空间复杂度的最优解法。题目核心需求判断一个单链表是否为回文链表回文即正序遍历与逆序遍历的节点值完全一致需兼顾时间、空间复杂度尤其需实现进阶要求的最优性能。一、题目详情1.1 题目描述给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。1.2 示例说明示例 1输入head [1,2,2,1]输出true解释链表正序为 1→2→2→1逆序为 1→2→2→1节点值完全一致属于回文链表。示例 2输入head [1,2]输出false解释链表正序为 1→2逆序为 2→1节点值不一致不属于回文链表。1.3 提示信息链表中节点数目在范围 [1, 10⁵] 内需考虑大数据量场景的性能问题节点值范围为 0 ≤ Node.val ≤ 9无负数简化值的比较逻辑进阶要求使用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题禁止使用额外数组/栈存储节点值。1.4 链表节点定义题目给定# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next next二、解题思路拆解回文的核心是“对称”对于单链表而言由于无法直接反向遍历不同于数组核心难点在于如何在不使用额外空间或少量空间的前提下对比链表的前半部分与后半部分节点值。本文将讲解两种解法基础解法借助数组存储节点值对比正逆序简单易实现空间复杂度O(n)进阶解法快慢指针找中点 反转后半链表 对比满足O(n)时间、O(1)空间。三、基础解法实现易理解适合入门3.1 思路说明利用数组的随机访问特性将链表的所有节点值依次存入数组然后通过双指针数组头、数组尾对比判断是否为回文。步骤遍历链表将每个节点的val存入数组初始化双指针 left0数组起始、rightlen(arr)-1数组末尾循环对比 arr[left] 和 arr[right]若有不相等则返回false若遍历结束均相等返回true。3.2 代码实现# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextfromtypingimportOptionalclassSolution:defisPalindrome(self,head:Optional[ListNode])-bool:# 步骤1将链表节点值存入数组val_list[]curheadwhilecur:val_list.append(cur.val)curcur.next# 步骤2双指针对比left,right0,len(val_list)-1whileleftright:ifval_list[left]!val_list[right]:returnFalseleft1right-1returnTrue3.3 复杂度分析时间复杂度O(n)遍历链表一次O(n)双指针遍历数组一次O(n)总时间为O(n)空间复杂度O(n)需额外存储n个节点值的数组不满足进阶要求但胜在简单易实现适合面试快速上手。3.4 示例验证示例1head [1,2,2,1] → val_list [1,2,2,1]双指针对比11、22返回true示例2head [1,2] → val_list [1,2]双指针对比1≠2返回false。四、进阶解法实现O(n)时间、O(1)空间最优解进阶要求禁止使用额外数组/栈核心思路是不存储节点值直接操作链表通过“找中点 反转后半链表 对比”实现回文判断全程无额外空间占用除几个指针变量。4.1 核心思路拆解找链表中点使用快慢指针快指针一次走2步慢指针一次走1步当快指针走到链表末尾时慢指针恰好走到链表中点偶数节点时慢指针走到前半段末尾反转后半链表将中点之后的链表反转得到后半段的逆序链表对比前后半链表从链表头部和反转后的后半链表头部依次对比节点值若全部相等则为回文可选恢复链表若题目要求不破坏原链表结构可在对比完成后再次反转后半链表恢复原链表本题无要求可省略。4.2 关键细节避坑点快慢指针初始化均从head开始快指针需判断fast.next和fast.next.next是否存在避免空指针异常偶数节点处理当链表节点数为偶数时慢指针走到前半段最后一个节点如[1,2,2,1]慢指针停在第二个2反转后半段后两个节点反转链表边界反转后半链表时需注意断开中点与后半段的连接避免链表循环。4.3 代码实现完整最优解# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextfromtypingimportOptionalclassSolution:defisPalindrome(self,head:Optional[ListNode])-bool:# 特殊情况空链表或单个节点直接返回trueifnotheadornothead.next:returnTrue# 步骤1快慢指针找链表中点slow,fasthead,head# 快指针走2步慢指针走1步直到快指针无法再走2步whilefast.nextandfast.next.next:slowslow.nextfastfast.next.next# 步骤2反转后半链表从slow.next开始defreverse_linked_list(node:Optional[ListNode])-Optional[ListNode]:prevNonecurnodewhilecur:# 保存下一个节点next_nodecur.next# 反转当前节点指针cur.nextprev# 移动指针prevcur curnext_node# prev为反转后的链表头returnprev# 反转后半链表得到反转后的头节点reverse_headreverse_linked_list(slow.next)# 断开前半段与后半段的连接避免循环slow.nextNone# 步骤3对比前半链表head开始和反转后的后半链表reverse_head开始cur1,cur2head,reverse_headwhilecur1andcur2:ifcur1.val!cur2.val:# 可选恢复原链表# slow.next reverse_linked_list(reverse_head)returnFalsecur1cur1.nextcur2cur2.next# 对比完成均相等返回true可选恢复原链表# slow.next reverse_linked_list(reverse_head)returnTrue4.4 复杂度分析时间复杂度O(n)快慢指针找中点O(n/2)、反转后半链表O(n/2)、对比前后半链表O(n/2)总时间为O(n)满足进阶要求空间复杂度O(1)仅使用几个指针变量slow、fast、cur1、cur2等无额外空间占用完全满足进阶要求。4.5 示例验证示例1head [1,2,2,1]快慢指针找中点slow停在第二个2index1fast停在最后一个1反转后半链表反转[2,1] → [1,2]reverse_head1对比head1→2与reverse_head1→2节点值均相等返回true。示例2head [1,2]快慢指针找中点slow停在1index0fast停在2反转后半链表反转[2] → [2]reverse_head2对比head1与reverse_head2值不相等返回false。五、常见问题与避坑指南5.1 空指针异常问题问题场景快慢指针循环条件写错、反转链表时未处理空节点。解决方案快慢指针循环条件必须是while fast.next and fast.next.next而非while fast and fast.next否则偶数节点时慢指针会多走一步反转链表时初始化prevNonecurnode循环条件为while cur避免cur为空时操作cur.next。5.2 链表节点数为1的处理问题场景当链表只有1个节点时直接返回true符合回文定义。解决方案在代码开头添加特殊判断if not head or not head.next: return True。5.3 进阶解法的链表破坏问题问题场景反转后半链表会破坏原链表结构若题目要求保留原链表需恢复。解决方案对比完成后再次反转后半链表将其接回原链表代码中已添加可选恢复逻辑注释打开即可。六、总结与拓展6.1 解法对比解法时间复杂度空间复杂度优点缺点基础解法数组存储O(n)O(n)简单易实现调试方便占用额外空间不满足进阶要求进阶解法快慢指针反转O(n)O(1)最优性能无额外空间逻辑稍复杂需注意边界处理6.2 面试建议面试时优先讲解基础解法快速展示思路再讲解进阶解法体现性能优化能力重点说明进阶解法的核心逻辑快慢指针找中点、反转链表以及避坑细节空指针、节点数奇偶性能让面试官看到你的思维深度和代码严谨性。6.3 拓展思考若链表节点值包含负数、字符串解法是否需要调整—— 无需调整仅需保证节点值可直接对比本题节点值为int可直接用对比。若链表长度极大10⁵节点进阶解法的优势是什么—— 无额外空间占用避免内存溢出运行效率更稳定。