【力扣100题】10.回文链表（C++ 解法）

一、题目描述

给定一个单链表的头节点head，判断该链表是否为回文链表。

示例

输入：head = [1,2,2,1] 输出：true 输入：head = [1,2] 输出：false

回文定义

简单来说，就是正着读和倒着读都一样。

二、核心思路

关键观察

判断回文，只需要比较前半部分和后半部分是否对称。

思路：找中点 → 翻转 → 对比

原链表: 1 -> 2 -> 2 -> 1 ↑ slow（中点） 步骤1：快慢指针找中点 - slow 走 1 步，fast 走 2 步 - fast 到尾时，slow 刚好在中点 步骤2：翻转后半部分 - 后半部分 2 -> 1 反转成 1 -> 2 步骤3：逐节点比较值 - 前半部分：1 -> 2 - 后半部分：1 -> 2 - 逐节点比较 val，相等则继续

三、代码实现

方法：快慢指针 + 反转（进阶最优解）✅

/** * 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) {} * }; */classSolution{public:boolisPalindrome(ListNode*head){// ========== 步骤1：快慢指针找中点 ==========ListNode dummy=ListNode(0,head);// 虚拟头节点ListNode*slow=&dummy;ListNode*fast=&dummy;while(fast&&fast->next){slow=slow->next;// slow 走 1 步fast=fast->next->next;// fast 走 2 步}// ========== 步骤2：翻转后半部分 ==========fast=slow->next;// fast 指向后半部分开头slow->next=nullptr;// 断开链表ListNode*pre=nullptr;while(fast){ListNode*cur=fast->next;// 保存下一个fast->next=pre;// 反转pre=fast;// 前进fast=cur;// 前进}// ========== 步骤3：比较前后两部分 ==========while(pre){// pre 是反转后的后半部分if(head->val!=pre->val)// 比较节点的值！returnfalse;head=head->next;pre=pre->next;}returntrue;}};

复杂度分析

四、图解全过程

示例：[1, 2, 2, 1]

原始链表：

1 -> 2 -> 2 -> 1 -> nullptr

步骤1：找中点

dummy -> 1 -> 2 -> 2 -> 1 -> nullptr ↑ ↑ slow fast 循环后： dummy -> 1 -> 2 -> 2 -> 1 -> nullptr ↑ ↑ slow fast(null)

步骤2：翻转后半部分

前半部分：1 -> 2 后半部分：2 -> 1 (original) 反转后后半：1 -> 2 链表变成： dummy -> 1 -> 2 -> nullptr ↑ slow 1 -> 2 (反转后的后半) ↑ pre

步骤3：比较

head(1) vs pre(1) ✓ head(2) vs pre(2) ✓ pre = nullptr，结束 返回 true ✓

示例：[1, 2](非回文)

比较：1 vs 2，不相等 返回 false ✓

五、为什么需要虚拟头节点？

ListNode dummy=ListNode(0,head);ListNode*slow=&dummy;ListNode*fast=&dummy;

使用dummy是为了统一处理，避免讨论head为空或只有一个节点的边界情况。

六、其他解法（不推荐）

方法2：数组比较（不满足进阶要求）

boolisPalindrome_array(ListNode*head){vector<int>vals;while(head){vals.push_back(head->val);head=head->next;}// 双指针比较intleft=0,right=vals.size()-1;while(left<right){if(vals[left++]!=vals[right--])returnfalse;}returntrue;}

七、方法对比

八、完整测试代码

#include<iostream>usingnamespacestd;structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}ListNode(intx):val(x),next(nullptr){}ListNode(intx,ListNode*next):val(x),next(next){}};classSolution{public:boolisPalindrome(ListNode*head){// 步骤1：找中点ListNode dummy=ListNode(0,head);ListNode*slow=&dummy;ListNode*fast=&dummy;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}// 步骤2：翻转后半部分fast=slow->next;slow->next=nullptr;ListNode*pre=nullptr;while(fast){ListNode*cur=fast->next;fast->next=pre;pre=fast;fast=cur;}// 步骤3：比较值while(pre){if(head->val!=pre->val)returnfalse;head=head->next;pre=pre->next;}returntrue;}};// 辅助函数：创建链表ListNode*createList(vector<int>vals){if(vals.empty())returnnullptr;ListNode*head=newListNode(vals[0]);ListNode*curr=head;for(inti=1;i<vals.size();i++){curr->next=newListNode(vals[i]);curr=curr->next;}returnhead;}intmain(){Solution sol;// 测试1：回文ListNode*head1=createList({1,2,2,1});cout<<"1,2,2,1 是回文? "<<(sol.isPalindrome(head1)?"true":"false")<<endl;// 测试2：非回文ListNode*head2=createList({1,2});cout<<"1,2 是回文? "<<(sol.isPalindrome(head2)?"true":"false")<<endl;// 测试3：单节点ListNode*head3=createList({1});cout<<"1 是回文? "<<(sol.isPalindrome(head3)?"true":"false")<<endl;return0;}

输出：

1,2,2,1 是回文? true 1,2 是回文? false 1 是回文? true

九、总结