1. 题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入： head = [1,2,2,1] 输出： true
示例 2：
输入： head = [1,2] 输出： false
2. 题解
2.1. 数组复制 + 双指针
2.1.1. 核心思想
链表不能随机访问，无法直接取末尾元素。先把链表所有节点的值拷贝到数组，利用数组支持下标随机访问的特性，再用双指针判断回文。
2.1.2. 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> temp;
ListNode* cur = head;
while(cur) {
temp.push_back(cur->val);
cur = cur->next;
}
int l = 0, r = temp.size() - 1;
while(l <= r) {
if(temp[l] != temp[r]) return false;
l++;
r--;
}
return true;
}
};2.1.3. 复杂度
时间复杂度： 空间复杂度： ，开辟数组存储全部链表元素
2.2. 递归
2.2.1. 核心思想
利用递归的栈回溯： 递归走到链表末尾（递归到底），然后从后往前返回；同时用一个外部指针从链表头部往后走。 递归返回时（相当于从链表尾部向前），和头部指针一一比较，实现一头一尾配对判断回文。
本质：递归调用栈把链表节点按顺序压栈，回溯就是逆序访问链表，模拟反转。 空间复杂度：(O(n))，递归调用栈深度等于链表长度。
2.2.2. 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* front;
bool isPalindrome(ListNode* head) {
front = head;
return check(head);
}
bool check(ListNode* cur) {
if(cur == nullptr) return true;
if(!check(cur->next)) return false;
if(front->val != cur->val) return false;
front = front->next;
return true;
}
};2.2.3. 复杂度
时间复杂度： ，每个节点访问一次 空间复杂度： ，递归调用栈，不是我们手动开数组，是系统栈
2.3. 快慢指针 + 反转后半段
2.3.1. 核心思想
- 快慢指针找链表中点：快指针一次走 2 步，慢指针一次走 1 步。快走到末尾时，慢指针恰好停在链表前半部分末尾。
- 反转后半段链表：把中点后面那一段链表反转，后半段就变成从尾向前。
- 双指针分别从头、从反转后的后半段开头，逐节点对比值。
- 比对完成，把后半段再次反转，恢复链表原有结构。
回文的性质：前半部分 = 后半部分的逆序。 把后半段反转之后，前半段和反转后的后半段就变成两个同向链表，可以直接一一比较。
2.3.2. 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
//边界：空链表 / 单个节点直接是回文
if (head == nullptr || head->next == nullptr) {
return true;
}
//1.快慢指针找中点
ListNode* slow = head;
ListNode* fast = head;
//循环条件：偶数slow停在前半末尾；奇数slow停在中间节点
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
//2.反转后半段链表，返回后半段新头
ListNode* secondHalf = reverse(slow->next);
//3.前后两段逐节点比较
ListNode* p1 = head;
ListNode* p2 = secondHalf;
bool result = true;
while (result && p2 != nullptr) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// 恢复链表：把后半段再次反转，恢复原始链表结构
slow->next = reverse(secondHalf);
return result;
}
//反转链表函数
ListNode* reverse(ListNode* cur) {
ListNode* pre = nullptr;
while (cur != nullptr) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};2.3.3. 复杂度
时间复杂度： ，找中点 、反转、比对，都是线性 空间复杂度： ，只使用有限几个指针变量，没有额外开辟容器，没有递归栈
2.4. 三种算法对比
| 实现方式 | 时间复杂度 | 空间复杂度 | 核心原理 | 优点 | 缺点 |
|---|---|---|---|---|---|
| 数组复制 + 双指针 | O(n) | O(n) | 将链表节点值拷贝数组；数组支持随机访问，左右双指针头尾向中间比对 | 逻辑最简单，代码简短，边界少，笔试快速写 | 需要额外数组存储数据；不是原地算法 |
| 递归法 | O(n) | O(n) | 递归深入到链表末尾，利用系统调用栈回溯实现从后往前遍历；外部指针从头向后，两两匹配 | 代码简洁，不需要手动反转链表 | 空间来自系统递归栈；链表很长会栈溢出；可读性差，一般不作为最优解 |
| 快慢指针 + 反转后半段 | O(n) | O(1) | 快慢指针找中点；反转后半段链表；双指针逐点比对；可二次反转恢复链表 | 原地算法，空间最优，面试标准解法 | 逻辑复杂，需要操作链表指针；会临时修改链表（可以恢复），边界容易写错 |