重生算法录|每日一题·回文链表

目录

🎯 闯关目标

解法1 开辟数组+“双指针”判断法

📈 复杂度深度分析

时间复杂度：O (n)

空间复杂度：O (n)

解法2 空间复杂度为O(1)的解法

🧠 闯关思路（核心脑洞）

📝 关键步骤拆解（趣味版）

🎮 测试用例闯关

⚡ 复杂度分析

🎁总结

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

示例 1：

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

示例 2：

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

提示：

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

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

🎯 闯关目标

判断一个无头节点单链表是不是回文（正着读和反着读一样，比如 1→2→2→1 是回文，1→2 不是）

解法1 开辟数组+“双指针”判断法

把链表的所有节点值「复制」到数组里，再用双指针法判断数组是不是回文（因为数组支持随机访问，对比超方便）。

c语言：

bool isPalindrome(struct ListNode* head) { int arr[1000] = {0}; int arr_nums = 0; while(head!= NULL){ arr[arr_nums++] = head -> val; head = head -> next; } int j = arr_nums - 1; for(int i = 0; i<j;i++,j--){ if(arr[i] != arr[j]){ return false; } } free(arr); return true; }

清理战场（释放数组内存）

• C 语言中malloc的内存不会自动释放，一定要用free(arr)，否则会造成内存泄漏（面试时漏写会扣分❌）。

📈 复杂度深度分析

时间复杂度：O (n)

• 统计节点数：遍历 1 次链表 → O (n)；
• 拷贝值到数组：遍历 1 次链表 → O (n)；
• 双指针对比：最多遍历 n/2 次 → O (n)；
• 总时间：O (n) + O (n) + O (n) = O (n)（忽略常数倍，只看最高阶）。

空间复杂度：O (n)

• 核心原因：开辟了一个长度为 n 的数组，数组占用的空间随链表节点数 n 线性增长。
• 其他变量都是单个指针 / 整数，占用固定内存（O (1)），不影响整体空间复杂度。

java版：

// 先定义链表节点类（LeetCode中会自动提供，不用自己写） class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class Solution { public boolean isPalindrome(ListNode head) { // 1. 替代C的int arr[1000]：Java用动态数组ArrayList更灵活（避免长度不够） // c原代码arr[1000]会有长度不足问题（题目节点数最多10^5），Java直接用动态数组搞定 java.util.ArrayList<Integer> arr = new java.util.ArrayList<>(); // 2. 遍历链表，把值存入数组（和C逻辑完全一致） ListNode curr = head; // Java不能直接修改入参head，用curr代替 while (curr != null) { arr.add(curr.val); // 对应C的arr[arr_nums++] = head->val curr = curr.next; } // 3. 双指针判断回文（和C逻辑一致） int i = 0; int j = arr.size() - 1; // 对应C的arr_nums - 1 while (i < j) { // 注意：Java中ArrayList取元素用get()，且要拆箱为int对比 if (arr.get(i) != arr.get(j)) { return false; } i++; j--; } return true; } }

解法2 空间复杂度为O(1)的解法

🧠 闯关思路（核心脑洞）

想象你有一根「糖葫芦」（链表）：1🍡2🍡2🍡1要判断是不是回文，不用把糖葫芦全拆下来（开数组），可以：

1. 🎡 找中点：用「快慢指针」把糖葫芦分成前后两半（1🍡2 和 2🍡1）
2. 🔄 反转后半段：把后半段翻过来变成 1🍡2
3. 🆚 对比两段：前半段 1🍡2 vs 反转后的后半段 1🍡2 → 一模一样就是回文！
4. 🔙 还原链表（可选但优雅）：把反转的后半段再翻回来，不破坏原链表

C语言版：

// 辅助函数：反转链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL, *curr = head, *next; while (curr != NULL) { next = curr->next; // 先抓着下一个节点，防止丢了 curr->next = prev; // 反转当前节点的指向 prev = curr; // 前驱指针往前走 curr = next; // 当前指针往前走 } return prev; // 反转后的新头节点 } // 主函数：判断回文链表 bool isPalindrome(struct ListNode* head) { // 🌰 特殊情况：空链表/只有1个节点，直接是回文 if (head == NULL || head->next == NULL) { return true; } // 1. 🎡 快慢指针找链表中点（慢指针最终停在左半段最后一个节点） struct ListNode *slow = head, *fast = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; // 慢指针走1步 fast = fast->next->next; // 快指针走2步 } // 2. 🔄 反转后半段链表 struct ListNode *second_half = reverseList(slow->next); struct ListNode *p1 = head; // 前半段起点 struct ListNode *p2 = second_half;// 后半段（反转后）起点 bool result = true; // 先默认是回文 // 3. 🆚 逐节点对比前后两段 while (result && p2 != NULL) { if (p1->val != p2->val) { result = false; // 发现不一样，不是回文 } p1 = p1->next; p2 = p2->next; } // 4. 🔙 还原后半段链表（可选，但是大厂面试加分项） slow->next = reverseList(second_half); return result; }

// 链表节点类（LeetCode中会自动提供，无需手写） class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class Solution { // 辅助方法：反转链表（对应C的reverseList函数） private ListNode reverseList(ListNode head) { ListNode prev = null; // 对应C的struct ListNode *prev = NULL ListNode curr = head; // 对应C的struct ListNode *curr = head ListNode next; // 对应C的struct ListNode *next while (curr != null) { // Java中用null代替C的NULL next = curr.next; // 保存下一个节点，防止丢失 curr.next = prev; // 反转当前节点的指向 prev = curr; // 前驱指针后移 curr = next; // 当前指针后移 } return prev; // 返回反转后的新头节点 } // 主方法：判断回文链表 public boolean isPalindrome(ListNode head) { // 特殊情况：空链表/单节点直接返回true if (head == null || head.next == null) { return true; } // 1. 快慢指针找链表中点（慢指针停在左半段最后一个节点） ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; // 慢指针走1步 fast = fast.next.next; // 快指针走2步 } // 2. 反转后半段链表 ListNode secondHalf = reverseList(slow.next); ListNode p1 = head; // 前半段起点 ListNode p2 = secondHalf; // 反转后的后半段起点 boolean result = true; // 默认是回文 // 3. 逐节点对比前后两段 while (result && p2 != null) { if (p1.val != p2.val) { // Java用.访问成员，C用-> result = false; } p1 = p1.next; p2 = p2.next; } // 4. 还原后半段链表（面试加分项） slow.next = reverseList(secondHalf); return result; } }

📝 关键步骤拆解（趣味版）

1. 找中点：快慢指针的 “龟兔赛跑”

• 🐢 慢指针（slow）：每次走 1 步，像乌龟慢慢爬
• 🐇 快指针（fast）：每次走 2 步，像兔子快速跑
• 当兔子跑到终点（fast->next/next 为 NULL），乌龟正好爬到链表中点（左半段最后一个节点）
  • 比如链表 1→2→2→1：兔子到第二个 2 时，乌龟停在第一个 2
  • 比如链表 1→2→3→2→1：兔子到 NULL 时，乌龟停在 3

2. 反转后半段：把糖葫芦倒过来

• 比如后半段 2→1，反转后变成 1→2
• 用reverseList函数：核心是 “断链 - 反转 - 衔接”，像解手链一样把指针方向反过来

3. 对比两段：逐个检查糖葫芦是不是一样

• 前半段 1→2 vs 反转后的后半段 1→2：每个节点值都一样 → 是回文
• 比如链表 1→2：前半段 1 vs 反转后的后半段 2 → 不一样 → 不是回文

4. 还原链表：做个有素质的程序员😜

• 面试时如果不还原，功能也对，但面试官会觉得你考虑不周全
• 把反转的后半段再反转一次，就恢复成原链表了

🎮 测试用例闯关

⚡ 复杂度分析

• ⏰ 时间复杂度 O (n)：找中点 O (n/2) + 反转 O (n/2) + 对比 O (n/2) → 总 O (n)
• 📦 空间复杂度 O (1)：只用到了几个指针变量，没开数组 / 栈，完美符合进阶要求！

🎁总结

1. 🧩 核心思路：找中点→反转后半段→对比→还原，用 “龟兔赛跑”+“反转链表” 实现 O (1) 空间
2. 🚨 关键细节：链表是无头节点的，head直接指向第一个有效节点，遍历从head开始
3. ✨ 面试加分项：处理特殊情况（空 / 单节点）+ 还原原链表，体现代码鲁棒性