LeetCode 算法：回文链表 c++

原题链接🔗：回文链表
难度：简单⭐️

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表中节点数目在范围[1, 10⁵] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题解

解决"回文链表"问题，我们可以采用以下几种解题思路：

1. 双指针法（快慢指针）

目的：找到链表的中点。
方法：使用两个指针，一个快指针（每次移动两个节点），一个慢指针（每次移动一个节点）。当快指针到达链表末尾时，慢指针即为中点。

2. 反转链表的后半部分

目的：将链表的后半部分反转，以便可以直接比较。
方法：从找到的中点开始，反转链表的后半部分。

3. 比较前半部分和反转后的后半部分

目的：判断链表是否是回文。
方法：使用两个指针，一个从链表头部开始，另一个从反转后的后半部分开始，逐个比较节点的值。

4. 恢复链表

目的：在判断完是否是回文后，恢复链表的原始结构。
方法：将反转的后半部分再次反转，以恢复链表的原始顺序。

5. 递归方法

目的：递归地比较链表的首尾元素，然后对剩余部分递归进行判断。
方法：定义一个递归函数，比较当前头节点和尾节点的值，如果相等，对子链表进行递归调用。

详细步骤

初始化两个指针：slow 和 fast，都指向头节点。
移动指针：fast 每次移动两个节点，slow 每次移动一个节点，直到 fast 到达链表末尾或其下一个节点。
反转链表的后半部分：从 slow 节点开始，反转链表的后半部分。
比较链表的前半部分和反转后的后半部分：使用两个指针，一个从链表头部开始，另一个从反转后的后半部分开始，逐个比较节点的值。
判断是否是回文：如果所有值都匹配，则链表是回文的；如果有不匹配的值，则链表不是回文的。
恢复链表：如果需要，将反转的后半部分再次反转，以恢复链表的原始顺序。

注意事项

在反转链表时，需要小心处理边界情况，如链表为空或只有一个节点。
在比较过程中，确保比较的是相同位置的节点。
如果使用递归方法，注意递归的终止条件和防止栈溢出。

通过上述步骤，你可以清晰地理解如何判断一个链表是否是回文，并选择适合的方法来实现算法。

快慢指针法

复杂度：时间复杂度O(n)，空间复杂度O(1)。
过程：

ListNode结构体：定义了链表的节点，包含整数值val和指向下一个节点的指针next。
Solution类：包含isPalindrome方法，用于判断链表是否是回文。
快慢指针：在isPalindrome方法中，使用快慢指针找到链表的中点。
反转链表：使用reverse辅助函数反转链表的后半部分。
比较：使用两个指针比较链表的前半部分和反转后的后半部分。
恢复链表：在比较完成后，再次调用reverse函数恢复链表的后半部分，以保持原始链表结构。
main函数：创建示例链表，调用isPalindrome方法，并输出结果。然后释放链表占用的内存。

c++ demo：

#include <iostream>// 定义链表节点
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};class Solution {
public:// 判断链表是否是回文bool isPalindrome(ListNode* head) {if (!head || !head->next) return true; // 空链表或只有一个节点是回文// 使用快慢指针找到链表中点ListNode* slow = head, * fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 反转链表的后半部分ListNode* secondHalf = reverse(slow);// 判断前半部分和反转后的后半部分是否相等ListNode* p1 = head, * p2 = secondHalf;bool isPalin = true;while (p2) {if (p1->val != p2->val) {isPalin = false;break;}p1 = p1->next;p2 = p2->next;}// 恢复链表的后半部分reverse(secondHalf);return isPalin;}private:// 反转链表的辅助函数ListNode* reverse(ListNode* head) {ListNode* prev = nullptr, * curr = head, * next = nullptr;while (curr) {next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}
};// 主函数，用于演示
int main() {Solution solution;// 创建一个示例链表: 1 -> 2 -> 2 -> 1ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(2);head->next->next->next = new ListNode(1);// 判断链表是否是回文bool isPalin = solution.isPalindrome(head);std::cout << (isPalin ? "链表是回文" : "链表不是回文") << std::endl;// 释放链表内存ListNode* current = head;while (current) {ListNode* next = current->next;delete current;current = next;}return 0;
}