【每日算法】LeetCode 234. 回文链表详解-平芜编程栈

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 234. 回文链表

1. 题目描述

给定一个单链表的头节点head，请判断该链表是否为回文链表。如果是，返回true；否则，返回false。

示例 1：

输入: head = [1,2,2,1] 输出: true

示例 2：

输入: head = [1,2] 输出: false

进阶要求：尝试使用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。

2. 问题分析

回文链表是指链表节点值从前往后读和从后往前读完全一致。作为前端开发者，我们常处理类似 DOM 树或组件状态树的结构，链表作为一种线性数据结构，在内存管理和优化中具有参考价值。

核心挑战：

链表单向遍历，无法直接反向访问。
需要在有限空间内高效比较节点值。
进阶要求 O(1) 空间，排除使用额外数组或栈等线性空间。

前端关联场景：例如，在虚拟 DOM 差异算法或状态历史管理中，检查结构对称性可优化渲染性能。

3. 解题思路

3.1 思路一：转换为数组法

将链表值复制到数组，再用双指针从两端向中间比较回文。

时间复杂度：O(n)
空间复杂度：O(n)
优点：简单直观，易于实现。
缺点：额外 O(n) 空间，不满足进阶要求。

3.2 思路二：递归法

利用递归栈隐式存储节点，从链表两端向内比较。

时间复杂度：O(n)
空间复杂度：O(n)（递归调用栈）
优点：代码简洁，体现递归思想。
缺点：栈空间 O(n)，可能栈溢出，不适合长链表。

3.3 思路三：快慢指针反转后半部分法（最优解）

使用快慢指针找到链表中点，反转后半部分链表，再比较前后两半是否一致。最后可选恢复链表。

时间复杂度：O(n)
空间复杂度：O(1)
优点：满足进阶要求，时间 O(n)、空间 O(1)。
缺点：修改链表结构，但可恢复。

4. 各思路代码实现

4.1 思路一：转换为数组法

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */functionisPalindrome(head){constarr=[];letcurr=head;while(curr!==null){arr.push(curr.val);curr=curr.next;}letleft=0,right=arr.length-1;while(left<right){if(arr[left]!==arr[right])returnfalse;left++;right--;}returntrue;}

4.2 思路二：递归法

functionisPalindrome(head){letfrontPointer=head;functionrecursivelyCheck(currentNode){if(currentNode!==null){if(!recursivelyCheck(currentNode.next))returnfalse;if(currentNode.val!==frontPointer.val)returnfalse;frontPointer=frontPointer.next;}returntrue;}returnrecursivelyCheck(head);}

4.3 思路三：快慢指针反转后半部分法

functionisPalindrome(head){if(head===null||head.next===null)returntrue;// 快慢指针找中点letslow=head,fast=head;while(fast.next!==null&&fast.next.next!==null){slow=slow.next;fast=fast.next.next;}// 反转后半部分链表letsecondHalfStart=reverseList(slow.next);// 比较前后两半letp1=head,p2=secondHalfStart;letisPal=true;while(p2!==null){if(p1.val!==p2.val){isPal=false;break;}p1=p1.next;p2=p2.next;}// 恢复链表（可选，保持原结构）slow.next=reverseList(secondHalfStart);returnisPal;}// 辅助函数：反转链表functionreverseList(head){letprev=null,curr=head;while(curr!==null){constnextTemp=curr.next;curr.next=prev;prev=curr;curr=nextTemp;}returnprev;}

5. 各实现思路的复杂度、优缺点对比表格

思路	时间复杂度	空间复杂度	优点	缺点	适用场景
转换为数组法	O(n)	O(n)	实现简单，快速原型开发	额外 O(n) 空间，不满足进阶要求	小规模数据或无需空间优化时
递归法	O(n)	O(n)	代码简洁，递归思维训练	递归栈 O(n)，可能栈溢出，性能较差	学习递归，链表长度有限时
快慢指针反转法	O(n)	O(1)	最优解，空间高效，满足进阶要求	需要修改链表（可恢复），实现稍复杂	大规模数据、内存敏感场景