当前位置：首页 > news >正文

【每天学习一点算法 2025/12/12】回文链表

news 2026/7/6 20:05:34

每天学习一点算法 2025/12/12

题目：回文链表

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

首先想到的方法就是将链表的值放到数组中再看他们是不是回文。

functionisPalindrome(head:ListNode|null):boolean{if(!head){returnfalse;}if(!head.next){returntrue;}conststack:number[]=[];lettem:ListNode|null=head;while(tem){stack.push(tem.val);tem=tem.next;}console.log(stack);returnstack.join("")===stack.reverse().join("");};

如果这个题目要用递归方法来解，我们要怎么做呢？老规矩

递：这个没啥好说，终止条件就是遍历完链表

归：我们这个时候回归处理就是从倒数节点开始处理了对吧？我们在归的过程中用另外一个指针从前往后移动，这样就是可以完成回文的比较了

functionisPalindrome(head:ListNode|null):boolean{// 边界条件提前处理：空链表/单节点直接返回trueif(head===null||head.next===null)returntrue;letfrontPointer:ListNode|null=head;constrecursivelyCheck=(currentNode:ListNode|null):boolean=>{// 终止条件：遍历到尾部，返回trueif(currentNode===null)returntrue;// 递归深入：先遍历到链表末端constisNextValid=recursivelyCheck(currentNode.next);// 提前短路：后续节点已判定非回文，直接返回falseif(!isNextValid)returnfalse;// 核心比较：当前递归节点（从后往前）与前向指针节点（从前往后）if(currentNode.val!==frontPointer!.val)returnfalse;// 前向指针后移frontPointer=frontPointer!.next;returntrue;};returnrecursivelyCheck(head);}