【忍者算法】从生活场景到回文链表：探索对称性检测｜LeetCode 234 回文链表

从生活场景到回文链表：探索对称性检测

生活中的回文现象

在日常生活中，回文无处不在。比如"上海自来水来自海上"、"12321"这样正着读和倒着读都一样的字符串或数字，就是回文。把这个概念扩展到链表，我们就得到了今天要讨论的回文链表问题：一个链表从前往后读和从后往前读的结果是否相同。
问题描述

LeetCode第234题"回文链表"要求：给你一个单链表的头节点 head，请判断该链表是否为回文链表。
例如：

1. 输入：1 → 2 → 2 → 1
2. 输出：true
4. 输入：1 → 2 → 3 → 2 → 1
5. 输出：true
7. 输入：1 → 2 → 3 → 3 → 1
8. 输出：false

复制代码

基础知识准备

这道题的核心是利用我们之前学过的"反转链表"。如果不熟悉链表反转，建议先复习上一篇文章。记住，链表反转是一块基石，在这里我们要用它来解决更复杂的问题。
直观解法：转换为数组

最简单的想法是：把链表转换成数组，然后用双指针从两端向中间移动比较。这就像把一摞扑克牌摊开在桌上，从两端开始对比每张牌是否相同。
数组法实现

1. public boolean isPalindrome(ListNode head) {
2.     List<Integer> vals = new ArrayList<>();
3.    
4.     // 将链表值复制到数组中
5.     ListNode current = head;
6.     while (current != null) {
7.         vals.add(current.val);
8.         current = current.next;
9.     }
10.    
11.     // 使用双指针判断是否回文
12.     int left = 0, right = vals.size() - 1;
13.     while (left < right) {
14.         if (!vals.get(left).equals(vals.get(right))) {
15.             return false;
16.         }
17.         left++;
18.         right--;
19.     }
20.    
21.     return true;
22. }

复制代码

优化解法：反转后半部分

仔细思考，我们其实不需要额外的数组。可以用这个巧妙的方法：

• 找到链表中点
  
• 反转后半部分
  
• 比较前后两半是否相同
  
• （可选）恢复链表原状
  

这就像把一叠纸牌分成两半，把后半部分倒过来，然后一张张对比。
寻找中点：快慢指针法

想象两个人在跑道上跑步，一个速度是另一个的两倍。当快跑者跑到终点时，慢跑者正好在中点！
详细代码实现

1. public boolean isPalindrome(ListNode head) {
2.     if (head == null || head.next == null) {
3.         return true;
4.     }
5.    
6.     // 第1步：找到中点
7.     ListNode slow = head;
8.     ListNode fast = head;
9.     while (fast.next != null && fast.next.next != null) {
10.         slow = slow.next;
11.         fast = fast.next.next;
12.     }
13.    
14.     // 第2步：反转后半部分
15.     ListNode secondHalf = reverseList(slow.next);
16.    
17.     // 第3步：比较两半是否相同
18.     ListNode firstHalf = head;
19.     ListNode temp = secondHalf; // 保存开始位置，用于之后恢复
20.     boolean result = true;
21.     while (secondHalf != null) {
22.         if (firstHalf.val != secondHalf.val) {
23.             result = false;
24.             break;
25.         }
26.         firstHalf = firstHalf.next;
27.         secondHalf = secondHalf.next;
28.     }
29.    
30.     // 第4步：恢复链表（可选）
31.     slow.next = reverseList(temp);
32.    
33.     return result;
34. }
36. // 链表反转函数（使用我们之前学过的方法）
37. private ListNode reverseList(ListNode head) {
38.     ListNode prev = null;
39.     ListNode curr = head;
40.     while (curr != null) {
41.         ListNode nextTemp = curr.next;
42.         curr.next = prev;
43.         prev = curr;
44.         curr = nextTemp;
45.     }
46.     return prev;
47. }

复制代码

图解过程

以1→2→3→2→1为例：

1. 1) 初始状态：
2. 1 → 2 → 3 → 2 → 1
4. 2) 找到中点：
5. 1 → 2 → [3] → 2 → 1
6. slow指向3
8. 3) 反转后半部分：
9. 1 → 2 → 3 ← 2 ← 1
11. 4) 比较两半：
12. (1 → 2) 和 (1 → 2) 比较
14. 5) 恢复原状：
15. 1 → 2 → 3 → 2 → 1

复制代码

复杂度分析

空间优化解法：

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)，只使用几个指针
  
• 优点：空间效率高，且思路优雅
  
• 缺点：修改了原链表结构（虽然最后恢复了）
  

重要思维方式总结

• 问题转化：将回文判断转化为对称性比较
  
• 空间优化思维：
  
  
  
  • 不用额外数组存储
    
  • 利用原有空间进行操作
    
  
  
• 分步思想：
  
  
  
  • 找中点（快慢指针）
    
  • 反转后半段（链表反转）
    
  • 对比（双指针）
    
  • 恢复（再次反转）
    
  
  
• 边界处理：
  
  
  
  • 空链表
    
  • 单节点链表
    
  • 偶数/奇数长度的处理
    
  
  

实用技巧总结

解决类似问题的关键点：

• 熟练掌握基础操作（如链表反转）
  
• 善用快慢指针找中点
  
• 考虑空间优化的可能性
  
• 注意保护原始数据结构
  

相关的思维训练：

• 回文数判断
  
• 回文子串问题
  
• 链表中点问题
  
• 链表反转的各种变体
  

小结

回文链表问题是一个很好的例子，展示了如何将基础算法（如链表反转、快慢指针）组合起来解决更复杂的问题。它教会我们：

• 基础算法的重要性
  
• 空间优化的思维方式
  
• 问题分解的方法
  
• 代码的优雅性
  

下次遇到类似的对称性判断问题，不要急着用额外空间，想想是否可以通过改变数据结构本身来解决问题！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！