链表----回文链表

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

<<Git>><<MySQL>>

🌟心向往之行必能至

LeetCode 234. 回文链表 —— 快慢指针 + 反转后半段，O(1) 空间优雅解法

题目难度：简单
标签：链表、双指针、反转链表
目标：判断单链表是否为回文结构，要求时间复杂度 O(n)，空间复杂度 O(1)

🔍 题目描述

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

示例：

1输入: head = [1,2,2,1] 2输出: true 3 4输入: head = [1,2] 5输出: false

💡 解题思路

要判断链表是否回文，最直观的方法是：

1. 遍历链表，将所有值存入数组 → 判断数组是否回文。
   • ✅ 简单易懂
   • ❌ 空间复杂度 O(n)，不符合“进阶”要求

我们追求的是O(1) 额外空间的解法，核心思想是：

找到链表中点 → 反转后半部分 → 前后两段逐个比较 → 恢复原链表（可选）

步骤详解：

Step 1：使用快慢指针找中点

• 定义slow和fast指针，都从头开始。
• fast每次走两步，slow每次走一步。
• 当fast到达末尾时，slow正好在中点（奇数长度时指向中间节点，偶数时指向前半段最后一个）。

Step 2：反转后半段链表

• 从slow->next开始反转后半段链表。
• 注意：如果链表长度为奇数，slow本身不参与比较，应从slow->next开始反转。

Step 3：前后两段逐一比较

• 前半段从头开始，后半段从反转后的头开始，逐个比较值。
• 若全部相等 → 是回文；否则不是。

Step 4（可选）：恢复链表结构

• 如果面试或生产环境要求不能修改原链表，可在比较完成后再次反转后半段，还原链表。

💻 C++ 代码实

1/** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11class Solution { 12public: 13 bool isPalindrome(ListNode* head) { 14 if (!head || !head->next) return true; 15 16 // Step 1: 找中点 17 ListNode* slow = head; 18 ListNode* fast = head; 19 while (fast->next && fast->next->next) { 20 slow = slow->next; 21 fast = fast->next->next; 22 } 23 24 // Step 2: 反转后半段 25 ListNode* secondHalf = reverseList(slow->next); 26 27 // Step 3: 比较前后两段 28 ListNode* p1 = head; 29 ListNode* p2 = secondHalf; 30 bool result = true; 31 while (p2) { 32 if (p1->val != p2->val) { 33 result = false; 34 break; 35 } 36 p1 = p1->next; 37 p2 = p2->next; 38 } 39 40 // Step 4（可选）: 恢复链表 41 slow->next = reverseList(secondHalf); 42 43 return result; 44 } 45 46private: 47 ListNode* reverseList(ListNode* head) { 48 ListNode* prev = nullptr; 49 ListNode* curr = head; 50 while (curr) { 51 ListNode* nextTemp = curr->next; 52 curr->next = prev; 53 prev = curr; 54 curr = nextTemp; 55 } 56 return prev; 57 } 58};

⏱️ 复杂度分析

• 时间复杂度：O(n)

  • 找中点：O(n/2)
  • 反转后半段：O(n/2)
  • 比较：O(n/2)
    → 总体 O(n)

• 空间复杂度：O(1)

  • 只使用了常数个指针变量，无额外数据结构

技巧总结

表格

📚 延伸思考

• 如果允许修改链表，是否可以省略“恢复”步骤？✅ 可以，但需注明。
• 如果链表非常长，如何优化缓存友好性？→ 可考虑分块处理或并行比较（高级话题）。
• 如何用递归解决？→ 递归本质是栈，空间 O(n)，不满足 O(1) 要求。