【力扣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 dummyListNode(0,head);// 虚拟头节点ListNode*slowdummy;ListNode*fastdummy;while(fastfast-next){slowslow-next;// slow 走 1 步fastfast-next-next;// fast 走 2 步}// 步骤2翻转后半部分 fastslow-next;// fast 指向后半部分开头slow-nextnullptr;// 断开链表ListNode*prenullptr;while(fast){ListNode*curfast-next;// 保存下一个fast-nextpre;// 反转prefast;// 前进fastcur;// 前进}// 步骤3比较前后两部分 while(pre){// pre 是反转后的后半部分if(head-val!pre-val)// 比较节点的值returnfalse;headhead-next;prepre-next;}returntrue;}};复杂度分析复杂度值说明时间O(n)遍历链表常数次空间O(1) ✅只用了几个指针四、图解全过程示例[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 dummyListNode(0,head);ListNode*slowdummy;ListNode*fastdummy;使用dummy是为了统一处理避免讨论head为空或只有一个节点的边界情况。不用 dummy用 dummy需要额外判断 head自动处理代码更复杂代码简洁六、其他解法不推荐方法2数组比较不满足进阶要求boolisPalindrome_array(ListNode*head){vectorintvals;while(head){vals.push_back(head-val);headhead-next;}// 双指针比较intleft0,rightvals.size()-1;while(leftright){if(vals[left]!vals[right--])returnfalse;}returntrue;}复杂度值时间O(n)空间O(n) ❌七、方法对比方法时间空间推荐度快慢指针 反转O(n)O(1) ✅⭐⭐⭐最优数组 双指针O(n)O(n)⭐⭐ 简单但空间不优八、完整测试代码#includeiostreamusingnamespacestd;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 dummyListNode(0,head);ListNode*slowdummy;ListNode*fastdummy;while(fastfast-next){slowslow-next;fastfast-next-next;}// 步骤2翻转后半部分fastslow-next;slow-nextnullptr;ListNode*prenullptr;while(fast){ListNode*curfast-next;fast-nextpre;prefast;fastcur;}// 步骤3比较值while(pre){if(head-val!pre-val)returnfalse;headhead-next;prepre-next;}returntrue;}};// 辅助函数创建链表ListNode*createList(vectorintvals){if(vals.empty())returnnullptr;ListNode*headnewListNode(vals[0]);ListNode*currhead;for(inti1;ivals.size();i){curr-nextnewListNode(vals[i]);currcurr-next;}returnhead;}intmain(){Solution sol;// 测试1回文ListNode*head1createList({1,2,2,1});cout1,2,2,1 是回文? (sol.isPalindrome(head1)?true:false)endl;// 测试2非回文ListNode*head2createList({1,2});cout1,2 是回文? (sol.isPalindrome(head2)?true:false)endl;// 测试3单节点ListNode*head3createList({1});cout1 是回文? (sol.isPalindrome(head3)?true:false)endl;return0;}输出1,2,2,1 是回文? true 1,2 是回文? false 1 是回文? true九、总结步骤操作关键点1快慢指针找中点fast 走 2 步slow 走 1 步2反转后半部分迭代法反转3比较节点值必须是head-val ! pre-val不是指针比较