题目介绍
给你一个单链表的头节点 \(head\) ，请你判断该链表是否为回文链表。如果是，返回 \(true\) ；否则，返回 \(false\) 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围\([1, 10^{5}]\) 内
- \(0 <= Node.val <= 9\)
进阶：你能否用 \(O(n)\) 时间复杂度和 \(O(1)\) 空间复杂度解决此题？
题解
2.1 双指针（链表转换数组）
代码
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> arr;
int i = 0, j =0;
while (head){
arr.push_back(head->val);
head = head ->next;
}
j = arr.size() - 1;
while (i < j){
if (arr[i++] != arr[j--]) return false;
}
return true;
}
};
复杂度分析
时间复杂度：O(n)，其中 nnn 指的是链表的元素个数。
第一步： 遍历链表并将值复制到数组中，O(n)。
第二步：双指针判断是否为回文，执行了 O(n/2） 次的判断，即 O(n)。
总的时间复杂度：O(2n)=O(n)O(2n) =O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。
2.2 递归
思路
回文链表最重要的是能同时拥有指向头尾的指针，方便进行比较。
我们联想到使用递归可以进入到最深层也就是尾结点，递归的回调也弥补了单向链表无法向前回溯的缺陷。然后在设置一个全局指向首节点的指针，使用双指针思路即可。
代码
class Solution {
ListNode *frontPointer;
public:
bool recursicvelyCheck(ListNode *currentNode){
if (currentNode != nullptr){ //回调返回条件：遍历到尾结点
if(!recursicvelyCheck(currentNode->next)) return false; //这里实现递归。如果出现一个不成立的情况，后续回调均返回false；
if(currentNode -> val != frontPointer -> val) return false; // 非回文链表情况。
frontPointer = frontPointer -> next; // 双指针的同步.
}
return true; //作为最深层的返回值
}
bool isPalindrome(ListNode* head) {
frontPointer = head;
return recursicvelyCheck(head);
}
};
复杂度分析
时间复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(n)，其中 n 指的是链表的大小。我们要理解计算机如何运行递归函数，在一个函数中调用一个函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。在进行回文检查之前，递归函数将在堆栈中创建 nnn 个堆栈帧，计算机会逐个弹出进行处理。所以在使用递归时空间复杂度要考虑堆栈的使用情况。
这种方法不仅使用了 O(n) 的空间，且比第一种方法更差，因为在许多语言中，堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小。