234. 回文链表
4 min
题目
解法：反转比较
思路
核心思想是使用快慢指针定位中点并反转前半部分链表。通过快指针（每次两步）和慢指针（每次一步）遍历，在慢指针移动时同步反转前半部分节点，使前半部分逆序。当快指针到达末尾时，慢指针位于中点（奇数长度需跳过中间节点），此时反转后的前半部分（prev）与后半部分（slow）应完全对称。
正确性基于回文序列的对称性：反转前半部分后，若为回文则前半部分逆序与后半部分正序应完全匹配。移动过程中反转操作保证了空间复杂度为O(1)，且不会遗漏最优解——因为中点定位准确且反转不改变节点值。
- Step 1: 快慢指针初始化，边遍历边反转前半部分（slow移动时修改指针指向）
- Step 2: 若链表长度奇数，slow后移跳过中间节点
- Step 3: 同步比较prev（反转前半）和slow（后半）的节点值
- Step 4: 发现不匹配立即返回false，否则遍历完成返回true
复杂度
- 时间复杂度: ，遍历链表两次（快慢指针一次，比较一次）
- 空间复杂度: ，仅使用固定数量的指针变量
代码
/**
* 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;
}
ListNode* slow = head;
ListNode* fast = head;
ListNode* prev = nullptr;
ListNode* temp = nullptr;
// 边遍历边反转前半部分
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
/**
* 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;
}
ListNode* slow = head;
ListNode* fast = head;
ListNode* prev = nullptr;
ListNode* temp = nullptr;
// 边遍历边反转前半部分
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
// 如果是奇数长度，fast 不为空，slow 指向中间节点
// 此时中间节点不参与比较，slow 需要后移一位
if (fast != nullptr) {
slow = slow->next;
}
// 比较反转后的前半部分 (prev) 和后半部分 (slow)
while (prev != nullptr && slow != nullptr) {
if (prev->val != slow->val) {
return false;
}
prev = prev->next;
slow = slow->next;
}
return true;
}
};