网站开发客户的思路总结,网络游戏企业不得向提供游戏服务,上海外贸商品交易会,专业的食品行业网站开发题目链接:234. 回文链表 - 力扣#xff08;LeetCode#xff09;
题目#xff1a; 题解#xff1a; currentNode 指针是先到尾节点#xff0c;由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val ! frontPointer.val 则返回 false。…题目链接:234. 回文链表 - 力扣LeetCode
题目 题解 currentNode 指针是先到尾节点由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val ! frontPointer.val 则返回 false。反之frontPointer 向前移动并返回 true。 算法的正确性在于递归处理节点的顺序是相反的回顾上面打印的算法而我们在函数外又记录了一个变量因此从本质上我们同时在正向和逆向迭代匹配。 时间复杂度O(n)其中 n 指的是链表的大小。 空间复杂度O(n)其中 n 指的是链表的大小。计算机在递归的过程中将使用堆栈的空间 (在进行回文检查之前递归函数将在堆栈中创建 n 个堆栈帧计算机会逐个弹出进行处理。所以在使用递归时空间复杂度要考虑堆栈的使用情况)。 代码
class Solution {ListNode* frontPointer;
public:bool check(ListNode* currentNode){if(currentNode!nullptr){if(!check(currentNode-next))//先递归到最后位置后逆向迭代{return false;}if(currentNode-val!frontPointer-val)//匹配是否为回文{return false;}frontPointerfrontPointer-next;//正向}return true;}bool isPalindrome(ListNode* head) {frontPointerhead; //保存第一个位置结点return check(head);}
};
