[Leetcode]同时进行正向和逆向迭代匹配解决回文链表问题

本文主要是介绍[Leetcode]同时进行正向和逆向迭代匹配解决回文链表问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接: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;}frontPointer=frontPointer->next;//正向}return true;}bool isPalindrome(ListNode* head) {frontPointer=head; //保存第一个位置结点return check(head);}
};

这篇关于[Leetcode]同时进行正向和逆向迭代匹配解决回文链表问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---