Java详解LeetCode 热题 100(24):LeetCode 234. 回文链表（Palindrome Linked List）详解

1. 题目描述

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

示例 1:

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

示例 2:

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

提示：

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

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

1.1 链表节点定义

/*** 单链表节点的定义*/
public class ListNode {int val;           // 节点的值ListNode next;     // 指向下一个节点的指针// 无参构造函数ListNode() {}// 带值的构造函数ListNode(int val) { this.val = val; }// 带值和下一个节点的构造函数ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

2. 理解题目

回文链表问题要求我们判断一个链表是否是"回文"的，即从左往右读和从右往左读是一样的。

什么是回文？

• 回文是指正读和反读都相同的字符序列
• 例如：1221、12321、aba 都是回文
• 对于链表：1->2->2->1 是回文，1->2->3->1 不是回文

关键特点：

1. 对称性：回文具有中心对称的特点
2. 双向一致：从头到尾和从尾到头的序列完全相同
3. 中心点：奇数长度有一个中心点，偶数长度有两个中心点

2.1 回文链表的特征

示例分析：

回文链表示例：

1 -> 2 -> 2 -> 1        (偶数长度)
1 -> 2 -> 3 -> 2 -> 1   (奇数长度)
5                       (单节点，回文)
7 -> 7                  (两个相同节点，回文)

非回文链表示例：

1 -> 2                  (不对称)
1 -> 2 -> 3             (不对称)
1 -> 2 -> 1 -> 3        (不对称)

2.2 核心难点

与字符串或数组不同，链表的难点在于：

1. 单向访问：只能从头到尾遍历，无法直接从尾到头
2. 无法随机访问：不能像数组那样通过索引直接访问任意位置
3. 空间约束：进阶要求 O(1) 空间复杂度

这些限制使得判断回文变得复杂，需要巧妙的算法设计。

3. 解法一：转换为数组法

3.1 算法思路

最直观的方法是将链表转换为数组，然后使用双指针判断是否为回文。

核心步骤：

1. 遍历链表，将所有节点值存储到数组中
2. 使用双指针（头尾指针）判断数组是否为回文
3. 左指针从头开始，右指针从尾开始，逐步向中间移动
4. 如果对应位置的值都相等，则为回文

3.2 详细图解

示例： 1 -> 2 -> 2 -> 1

步骤1：链表转数组
链表：1 -> 2 -> 2 -> 1
数组：[1, 2, 2, 1]↑        ↑left     right步骤2：双指针比较
第1次比较：arr[0]=1, arr[3]=1 ✓ 相等left++, right--
第2次比较：arr[1]=2, arr[2]=2 ✓ 相等left++, right--
第3次：left >= right，结束，返回true

3.3 Java代码实现

import java.util.ArrayList;
import java.util.List;/*** 解法一：转换为数组法* 时间复杂度：O(n)，遍历链表一次，遍历数组一次* 空间复杂度：O(n)，需要额外数组存储链表值*/
class Solution1 {public boolean isPalindrome(ListNode head) {// 边界条件：空链表或单节点链表都是回文if (head == null || head.next == null) {return true;}// 步骤1：将链表转换为数组List<Integer> values = new ArrayList<>();ListNode curr = head;while (curr != null) {values.add(curr.val);curr = curr.next;}// 步骤2：使用双指针判断数组是否为回文int left = 0;int right = values.size() - 1;while (left < right) {// 如果对应位置的值不相等，不是回文if (!values.get(left).equals(values.get(right))) {return false;}left++;right--;}return true;}
}

3.4 详细执行过程演示

/*** 带详细调试输出的数组法实现*/
public class ArrayMethodDemo {public boolean isPalindrome(ListNode head) {System.out.println("=== 数组法判断回文链表 ===");System.out.println("原链表：" + printList(head));if (head == null || head.next == null) {System.out.println("边界条件：空链表或单节点，返回 true");return true;}// 转换为数组List<Integer> values = new ArrayList<>();ListNode curr = head;System.out.println("\n步骤1：链表转数组");while (curr != null) {values.add(curr.val);System.out.println("  添加值: " + curr.val + " -> 数组: " + values);curr = curr.next;}System.out.println("最终数组: " + values);// 双指针判断System.out.println("\n步骤2：双指针判断回文");int left = 0;int right = values.size() - 1;int step = 1;while (left < right) {int leftVal = values.get(left);int rightVal = values.get(right);System.out.println("第" + step + "次比较:");System.out.println("  left=" + left + ", right=" + right);System.out.println("  values[" + left + "]=" + leftVal + ", values[" + right + "]=" + rightVal);if (leftVal != rightVal) {System.out.println("  不相等！不是回文，返回 false");return false;}System.out.println("  相等！继续比较...");left++;right--;step++;}System.out.println("所有比较完成，是回文链表，返回 true");return true;}// 辅助方法：打印链表private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");ListNode curr = head;while (curr != null) {sb.append(curr.val);if (curr.next != null) sb.append(" -> ");curr = curr.next;}sb.append("]");return sb.toString();}
}

3.5 执行结果示例

输入： [1,2,2,1]

=== 数组法判断回文链表 ===
原链表：[1 -> 2 -> 2 -> 1]步骤1：链表转数组添加值: 1 -> 数组: [1]添加值: 2 -> 数组: [1, 2]添加值: 2 -> 数组: [1, 2, 2]添加值: 1 -> 数组: [1, 2, 2, 1]
最终数组: [1, 2, 2, 1]步骤2：双指针判断回文
第1次比较:left=0, right=3values[0]=1, values[3]=1相等！继续比较...
第2次比较:left=1, right=2values[1]=2, values[2]=2相等！继续比较...
所有比较完成，是回文链表，返回 true

3.6 使用数组而非ArrayList的优化版本

/*** 使用固定数组的优化版本* 避免ArrayList的装箱开销*/
class Solution1Optimized {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 首先计算链表长度int length = getLength(head);// 创建固定大小的数组int[] values = new int[length];// 填充数组ListNode curr = head;for (int i = 0; i < length; i++) {values[i] = curr.val;curr = curr.next;}// 双指针判断回文for (int i = 0; i < length / 2; i++) {if (values[i] != values[length - 1 - i]) {return false;}}return true;}private int getLength(ListNode head) {int length = 0;while (head != null) {length++;head = head.next;}return length;}
}

3.7 复杂度分析

时间复杂度： O(n)

• 遍历链表一次：O(n)
• 双指针遍历数组：O(n/2) = O(n)
• 总时间复杂度：O(n)

空间复杂度： O(n)

• 需要额外的数组或列表存储链表的所有值
• 空间消耗与链表长度成正比

3.8 优缺点分析

优点：

1. 思路简单：最直观易懂的解法
2. 实现容易：代码简洁，不易出错
3. 稳定可靠：逻辑清晰，边界情况容易处理

缺点：

1. 空间消耗大：需要O(n)额外空间
2. 不满足进阶要求：无法达到O(1)空间复杂度
3. 两次遍历：需要遍历链表和数组各一次

4. 解法二：递归法

4.1 递归思路

递归方法的核心思想是利用递归的特性，在回溯过程中从后往前比较节点值。

核心原理：

1. 递归到达链表末尾
2. 在回溯过程中，从后往前依次比较节点
3. 使用一个全局指针从前往后移动，与递归回溯的节点进行比较

递归过程分析：
对于链表 1 -> 2 -> 2 -> 1：

递归前进：1 -> 2 -> 2 -> 1 -> null
递归回溯：null <- 1 <- 2 <- 2 <- 1
比较顺序：(1,1) -> (2,2) -> 对称匹配

4.2 Java递归实现

/*** 解法二：递归法* 时间复杂度：O(n)，递归遍历每个节点一次* 空间复杂度：O(n)，递归调用栈的深度为链表长度*/
class Solution2 {private ListNode frontPointer;  // 前向指针，用于与递归回溯的节点比较public boolean isPalindrome(ListNode head) {frontPointer = head;return recursivelyCheck(head);}private boolean recursivelyCheck(ListNode currentNode) {// 递归终止条件：到达链表末尾if (currentNode != null) {// 递归前进到下一个节点if (!recursivelyCheck(currentNode.next)) {return false;  // 如果子问题返回false，直接返回false}// 在递归回溯过程中进行比较if (currentNode.val != frontPointer.val) {return false;  // 值不相等，不是回文}// 前向指针向前移动frontPointer = frontPointer.next;}return true;  // 到达链表末尾或所有比较都成功}
}

4.3 递归过程详细演示

/*** 带详细调试输出的递归法实现*/
public class RecursiveMethodDemo {private ListNode frontPointer;private int depth = 0;  // 递归深度计数器public boolean isPalindrome(ListNode head) {System.out.println("=== 递归法判断回文链表 ===");System.out.println("原链表：" + printList(head));frontPointer = head;boolean result = recursivelyCheck(head);System.out.println("最终结果：" + (result ? "是回文" : "不是回文"));return result;}private boolean recursivelyCheck(ListNode currentNode) {String indent = "  ".repeat(depth);  // 缩进显示递归层次System.out.println(indent + "→ 进入递归 depth=" + depth + ", 当前节点: " + (currentNode == null ? "null" : currentNode.val) +", 前向指针: " + (frontPointer == null ? "null" : frontPointer.val));// 递归终止条件if (currentNode == null) {System.out.println(indent + "← 到达链表末尾，开始回溯");return true;}depth++;  // 递归深度增加// 递归前进System.out.println(indent + "递归前进到下一个节点...");boolean result = recursivelyCheck(currentNode.next);depth--;  // 递归深度减少if (!result) {System.out.println(indent + "← 子递归返回false，不是回文");return false;}// 在回溯过程中进行比较System.out.println(indent + "← 回溯比较: currentNode=" + currentNode.val + ", frontPointer=" + frontPointer.val);if (currentNode.val != frontPointer.val) {System.out.println(indent + "← 值不相等，不是回文");return false;}System.out.println(indent + "← 值相等，继续...");frontPointer = frontPointer.next;System.out.println(indent + "← 前向指针移动到: " + (frontPointer == null ? "null" : frontPointer.val));return true;}private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");ListNode curr = head;while (curr != null) {sb.append(curr.val);if (curr.next != null) sb.append(" -> ");curr = curr.next;}sb.append("]");return sb.toString();}
}

4.4 递归执行过程

输入： [1,2,2,1]

=== 递归法判断回文链表 ===
原链表：[1 -> 2 -> 2 -> 1]→ 进入递归 depth=0, 当前节点: 1, 前向指针: 1
递归前进到下一个节点...→ 进入递归 depth=1, 当前节点: 2, 前向指针: 1递归前进到下一个节点...→ 进入递归 depth=2, 当前节点: 2, 前向指针: 1递归前进到下一个节点...→ 进入递归 depth=3, 当前节点: 1, 前向指针: 1递归前进到下一个节点...→ 进入递归 depth=4, 当前节点: null, 前向指针: 1← 到达链表末尾，开始回溯← 回溯比较: currentNode=1, frontPointer=1← 值相等，继续...← 前向指针移动到: 2← 回溯比较: currentNode=2, frontPointer=2← 值相等，继续...← 前向指针移动到: 2← 回溯比较: currentNode=2, frontPointer=2← 值相等，继续...← 前向指针移动到: 1
← 回溯比较: currentNode=1, frontPointer=1
← 值相等，继续...
← 前向指针移动到: null
最终结果：是回文

4.5 递归算法的关键理解

1. 双向遍历模拟：

   • 递归前进模拟从左到右遍历
   • 递归回溯模拟从右到左遍历
   • frontPointer 在回溯过程中从左向右移动

2. 对称比较：

   // 回溯时的比较顺序
   // 第1次回溯：最后一个节点 vs 第一个节点
   // 第2次回溯：倒数第二个节点 vs 第二个节点
   // ...
   

3. 状态传递：

   • 使用类成员变量 frontPointer 保持状态
   • 递归返回值传递子问题的结果

4.6 复杂度分析

时间复杂度： O(n)

• 每个节点被访问一次，总共 n 次递归调用
• 每次递归的操作都是常数时间

空间复杂度： O(n)

• 递归调用栈的深度为 n（链表长度）
• 每层递归需要常数级的额外空间

4.7 递归法的优缺点

优点：

1. 思路巧妙：利用递归栈模拟反向遍历
2. 代码简洁：相对于其他方法，代码量较少
3. 逻辑清晰：递归思想符合问题的对称特性

缺点：

1. 空间开销大：需要 O(n) 的递归栈空间
2. 可能栈溢出：对于很长的链表，可能导致栈溢出
3. 理解难度高：递归思维对初学者较难理解
4. 不满足进阶要求：无法达到 O(1) 空间复杂度

5. 解法三：栈方法

5.1 栈的思路

栈是一种后进先出（LIFO）的数据结构，可以帮助我们实现链表的"反向访问"。

核心思想：

1. 第一次遍历：将链表的前半部分节点值压入栈
2. 第二次遍历：将链表的后半部分与栈中弹出的值进行比较
3. 如果所有比较都相等，则为回文

关键点：

• 需要先找到链表的中点
• 奇数长度链表需要跳过中间节点
• 栈的特性天然提供了"反向"访问

5.2 详细图解

示例： 1 -> 2 -> 3 -> 2 -> 1（奇数长度）

步骤1：找到中点并将前半部分入栈
链表：1 -> 2 -> 3 -> 2 -> 1↑    ↑    ↑入栈  入栈  中点(跳过)栈状态：[1, 2]  (栈顶是2)步骤2：遍历后半部分，与栈顶比较
比较1：节点2 vs 栈顶2 ✓ 相等，弹出栈顶
比较2：节点1 vs 栈顶1 ✓ 相等，弹出栈顶
栈为空，全部匹配，是回文

5.3 Java代码实现

import java.util.Stack;/*** 解法三：栈方法* 时间复杂度：O(n)，需要遍历链表两次* 空间复杂度：O(n/2) = O(n)，栈存储链表前半部分*/
class Solution3 {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 步骤1：使用快慢指针找到中点ListNode slow = head;ListNode fast = head;Stack<Integer> stack = new Stack<>();// 将前半部分压入栈，同时找到中点while (fast != null && fast.next != null) {stack.push(slow.val);slow = slow.next;fast = fast.next.next;}// 如果链表长度为奇数，跳过中间节点if (fast != null) {slow = slow.next;}// 步骤2：比较后半部分与栈中的值while (slow != null) {if (stack.isEmpty() || slow.val != stack.pop()) {return false;}slow = slow.next;}return stack.isEmpty();  // 栈应该为空}
}

5.4 详细执行过程演示

/*** 带详细调试输出的栈方法实现*/
public class StackMethodDemo {public boolean isPalindrome(ListNode head) {System.out.println("=== 栈方法判断回文链表 ===");System.out.println("原链表：" + printList(head));if (head == null || head.next == null) {System.out.println("边界条件：空链表或单节点，返回 true");return true;}// 使用快慢指针找中点，同时将前半部分入栈ListNode slow = head;ListNode fast = head;Stack<Integer> stack = new Stack<>();System.out.println("\n步骤1：快慢指针找中点，前半部分入栈");int step = 1;while (fast != null && fast.next != null) {System.out.println("第" + step + "轮:");System.out.println("  slow指向: " + slow.val + ", fast指向: " + fast.val);System.out.println("  将 " + slow.val + " 压入栈");stack.push(slow.val);slow = slow.next;fast = fast.next.next;System.out.println("  移动指针后 slow指向: " + (slow == null ? "null" : slow.val) + ", fast指向: " + (fast == null ? "null" : fast.val));System.out.println("  当前栈状态: " + stack);System.out.println();step++;}// 判断链表长度是否为奇数if (fast != null) {System.out.println("链表长度为奇数，跳过中间节点: " + slow.val);slow = slow.next;} else {System.out.println("链表长度为偶数，无需跳过中间节点");}System.out.println("前半部分入栈完成，栈状态: " + stack);System.out.println("开始比较后半部分...");// 比较后半部分与栈中的值System.out.println("\n步骤2：比较后半部分与栈顶元素");step = 1;while (slow != null) {if (stack.isEmpty()) {System.out.println("第" + step + "次比较: 栈已空但链表未结束，不是回文");return false;}int stackTop = stack.peek();System.out.println("第" + step + "次比较:");System.out.println("  当前节点值: " + slow.val);System.out.println("  栈顶元素: " + stackTop);if (slow.val != stackTop) {System.out.println("  不相等，不是回文，返回 false");return false;}stack.pop();System.out.println("  相等，弹出栈顶，继续比较...");System.out.println("  弹出后栈状态: " + stack);slow = slow.next;step++;}boolean isEmpty = stack.isEmpty();System.out.println("\n比较完成，栈" + (isEmpty ? "为空" : "不为空"));System.out.println("结果: " + (isEmpty ? "是回文" : "不是回文"));return isEmpty;}private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");ListNode curr = head;while (curr != null) {sb.append(curr.val);if (curr.next != null) sb.append(" -> ");curr = curr.next;}sb.append("]");return sb.toString();}
}

5.5 执行结果示例

输入： [1,2,3,2,1]（奇数长度）

=== 栈方法判断回文链表 ===
原链表：[1 -> 2 -> 3 -> 2 -> 1]步骤1：快慢指针找中点，前半部分入栈
第1轮:slow指向: 1, fast指向: 1将 1 压入栈移动指针后 slow指向: 2, fast指向: 3当前栈状态: [1]第2轮:slow指向: 2, fast指向: 3将 2 压入栈移动指针后 slow指向: 3, fast指向: null当前栈状态: [1, 2]链表长度为奇数，跳过中间节点: 3
前半部分入栈完成，栈状态: [1, 2]
开始比较后半部分...步骤2：比较后半部分与栈顶元素
第1次比较:当前节点值: 2栈顶元素: 2相等，弹出栈顶，继续比较...弹出后栈状态: [1]
第2次比较:当前节点值: 1栈顶元素: 1相等，弹出栈顶，继续比较...弹出后栈状态: []比较完成，栈为空
结果: 是回文

5.6 处理偶数长度的示例

输入： [1,2,2,1]（偶数长度）

=== 栈方法判断回文链表 ===
原链表：[1 -> 2 -> 2 -> 1]步骤1：快慢指针找中点，前半部分入栈
第1轮:slow指向: 1, fast指向: 1将 1 压入栈移动指针后 slow指向: 2, fast指向: 2当前栈状态: [1]第2轮:slow指向: 2, fast指向: 2将 2 压入栈移动指针后 slow指向: 2, fast指向: null当前栈状态: [1, 2]链表长度为偶数，无需跳过中间节点
前半部分入栈完成，栈状态: [1, 2]
开始比较后半部分...步骤2：比较后半部分与栈顶元素
第1次比较:当前节点值: 2栈顶元素: 2相等，弹出栈顶，继续比较...弹出后栈状态: [1]
第2次比较:当前节点值: 1栈顶元素: 1相等，弹出栈顶，继续比较...弹出后栈状态: []比较完成，栈为空
结果: 是回文

5.7 复杂度分析

时间复杂度： O(n)

• 第一次遍历找中点并入栈：O(n/2)
• 第二次遍历比较后半部分：O(n/2)
• 总时间复杂度：O(n)

空间复杂度： O(n)

• 栈中存储链表前半部分的值：O(n/2) = O(n)
• 其他变量使用常数空间：O(1)

5.8 栈方法的优缺点

优点：

1. 思路直观：栈的LIFO特性天然适合回文判断
2. 实现简单：代码逻辑清晰，容易理解
3. 一次遍历：只需要遍历链表一次半（一次完整+半次比较）

缺点：

1. 空间消耗：需要O(n)额外空间存储栈
2. 不满足进阶要求：无法达到O(1)空间复杂度
3. 需要额外数据结构：依赖栈这种额外的数据结构

6. 解法四：快慢指针 + 反转链表法（最优解）

6.1 最优算法思路

这是满足进阶要求（O(1)空间复杂度）的最优解法，核心思想是：

1. 使用快慢指针找到链表中点
2. 反转链表的后半部分
3. 同时遍历前半部分和反转后的后半部分进行比较
4. 恢复链表结构（可选）

关键优势：

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 满足所有题目要求

6.2 详细图解

示例： 1 -> 2 -> 2 -> 1（偶数长度）

步骤1：快慢指针找中点
初始：   1 -> 2 -> 2 -> 1slow fast第1轮：   1 -> 2 -> 2 -> 1slow    fast第2轮：   1 -> 2 -> 2 -> 1slow    (fast到达末尾)步骤2：反转后半部分
原始：   1 -> 2 -> 2 -> 1↑ 中点后反转后： 1 -> 2    1 -> 2↑    ↑前半部  后半部(反转)步骤3：双指针比较
前半部：1 -> 2
后半部：1 -> 2
逐一比较：(1,1)✓ (2,2)✓ -> 是回文

6.3 Java代码实现

/*** 解法四：快慢指针 + 反转链表法（最优解）* 时间复杂度：O(n)，遍历链表常数次* 空间复杂度：O(1)，只使用常数级额外空间*/
class Solution4 {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 步骤1：使用快慢指针找到链表中点ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 步骤2：反转链表的后半部分ListNode secondHalf = reverseList(slow);// 步骤3：比较前半部分和反转后的后半部分ListNode firstHalf = head;ListNode reversedSecondHalf = secondHalf;  // 保存反转后的头节点boolean isPalin = true;while (secondHalf != null) {if (firstHalf.val != secondHalf.val) {isPalin = false;break;}firstHalf = firstHalf.next;secondHalf = secondHalf.next;}// 步骤4：恢复链表结构（可选）reverseList(reversedSecondHalf);return isPalin;}/*** 反转链表的辅助方法*/private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

6.4 详细执行过程演示

/*** 带详细调试输出的最优解法实现*/
public class OptimalMethodDemo {public boolean isPalindrome(ListNode head) {System.out.println("=== 最优解法：快慢指针+反转链表 ===");System.out.println("原链表：" + printList(head));if (head == null || head.next == null) {System.out.println("边界条件：空链表或单节点，返回 true");return true;}// 步骤1：快慢指针找中点System.out.println("\n步骤1：使用快慢指针找到中点");ListNode slow = head;ListNode fast = head;int round = 1;while (fast != null && fast.next != null) {System.out.println("第" + round + "轮:");System.out.println("  slow指向: " + slow.val + ", fast指向: " + fast.val);slow = slow.next;fast = fast.next.next;System.out.println("  移动后 slow指向: " + (slow == null ? "null" : slow.val) + ", fast指向: " + (fast == null ? "null" : fast.val));round++;}System.out.println("找到中点位置，slow指向: " + slow.val);System.out.println("后半部分为: " + printList(slow));// 步骤2：反转后半部分System.out.println("\n步骤2：反转后半部分");ListNode secondHalf = reverseListWithDebug(slow);System.out.println("反转后的后半部分: " + printList(secondHalf));// 步骤3：双指针比较System.out.println("\n步骤3：双指针比较前后两部分");ListNode firstHalf = head;ListNode reversedSecondHalf = secondHalf;boolean isPalin = true;int compareRound = 1;while (secondHalf != null) {System.out.println("第" + compareRound + "次比较:");System.out.println("  前半部分: " + firstHalf.val + ", 后半部分: " + secondHalf.val);if (firstHalf.val != secondHalf.val) {System.out.println("  不相等，不是回文！");isPalin = false;break;}System.out.println("  相等，继续比较...");firstHalf = firstHalf.next;secondHalf = secondHalf.next;compareRound++;}// 步骤4：恢复链表System.out.println("\n步骤4：恢复链表结构");reverseListWithDebug(reversedSecondHalf);System.out.println("恢复后的链表: " + printList(head));System.out.println("\n最终结果: " + (isPalin ? "是回文" : "不是回文"));return isPalin;}private ListNode reverseListWithDebug(ListNode head) {System.out.println("  反转链表: " + printList(head));ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}System.out.println("  反转结果: " + printList(prev));return prev;}private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");ListNode curr = head;while (curr != null) {sb.append(curr.val);if (curr.next != null) sb.append(" -> ");curr = curr.next;}sb.append("]");return sb.toString();}
}

6.5 执行结果示例

输入： [1,2,2,1]

=== 最优解法：快慢指针+反转链表 ===
原链表：[1 -> 2 -> 2 -> 1]步骤1：使用快慢指针找到中点
第1轮:slow指向: 1, fast指向: 1移动后 slow指向: 2, fast指向: 2
第2轮:slow指向: 2, fast指向: 2移动后 slow指向: 2, fast指向: null
找到中点位置，slow指向: 2
后半部分为: [2 -> 1]步骤2：反转后半部分反转链表: [2 -> 1]反转结果: [1 -> 2]
反转后的后半部分: [1 -> 2]步骤3：双指针比较前后两部分
第1次比较:前半部分: 1, 后半部分: 1相等，继续比较...
第2次比较:前半部分: 2, 后半部分: 2相等，继续比较...步骤4：恢复链表反转链表: [1 -> 2]反转结果: [2 -> 1]
恢复后的链表: [1 -> 2 -> 2 -> 1]最终结果: 是回文

6.6 处理奇数长度链表

/*** 专门处理奇数长度链表的示例*/
public void demonstrateOddLength() {// 构造奇数长度链表: [1,2,3,2,1]ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(2);head.next.next.next.next = new ListNode(1);System.out.println("=== 奇数长度链表示例 ===");System.out.println("原链表：[1 -> 2 -> 3 -> 2 -> 1]");System.out.println("中间节点不参与比较，只比较前后对称部分");/*对于奇数长度链表 1->2->3->2->1：- 快慢指针结束时，slow指向中间节点3- 反转后半部分：3->2->1 变成 1->2->3- 比较：前半部分1->2 与 反转后1->2- 中间节点3不参与比较*/
}

6.7 不恢复链表的简化版本

/*** 不恢复链表结构的简化版本* 适用于不需要保持原链表结构的场景*/
class Solution4Simplified {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 快慢指针找中点ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 反转后半部分ListNode secondHalf = reverseList(slow);// 比较前后两部分ListNode firstHalf = head;while (secondHalf != null) {if (firstHalf.val != secondHalf.val) {return false;}firstHalf = firstHalf.next;secondHalf = secondHalf.next;}return true;}private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

6.8 复杂度分析

时间复杂度： O(n)

• 找中点：O(n/2)
• 反转后半部分：O(n/2)
• 比较两部分：O(n/2)
• 恢复链表：O(n/2)
• 总时间复杂度：O(n)

空间复杂度： O(1)

• 只使用常数级的额外变量（指针）
• 不需要额外的数据结构

6.9 最优解法的优缺点

优点：

1. 空间最优：O(1)空间复杂度，满足进阶要求
2. 时间高效：O(n)时间复杂度
3. 实用性强：适合内存受限的环境
4. 面试首选：展示了链表操作的多种技巧

缺点：

1. 实现复杂：需要掌握快慢指针和链表反转
2. 破坏结构：会临时改变链表结构
3. 理解门槛：对新手来说有一定难度

7. 完整测试用例和边界处理

7.1 完整测试代码

/*** 回文链表完整测试类*/
public class PalindromeListTest {public static void main(String[] args) {PalindromeListTest test = new PalindromeListTest();System.out.println("=== 回文链表测试套件 ===\n");// 运行所有测试用例test.testCase1_EmptyAndSingle();test.testCase2_TwoNodes();test.testCase3_EvenPalindrome();test.testCase4_OddPalindrome();test.testCase5_NotPalindrome();test.testCase6_LargePalindrome();test.testCase7_PerformanceTest();System.out.println("=== 所有测试完成 ===");}/*** 测试用例1：空链表和单节点*/public void testCase1_EmptyAndSingle() {System.out.println("【测试用例1】空链表和单节点");// 空链表System.out.println("子测试1：空链表");testAllMethods(null, true);// 单节点System.out.println("子测试2：单节点 [5]");ListNode single = new ListNode(5);testAllMethods(single, true);System.out.println();}/*** 测试用例2：两个节点*/public void testCase2_TwoNodes() {System.out.println("【测试用例2】两个节点");// 相同的两个节点System.out.println("子测试1：相同节点 [1,1]");ListNode same = buildList(new int[]{1, 1});testAllMethods(same, true);// 不同的两个节点System.out.println("子测试2：不同节点 [1,2]");ListNode diff = buildList(new int[]{1, 2});testAllMethods(diff, false);System.out.println();}/*** 测试用例3：偶数长度回文*/public void testCase3_EvenPalindrome() {System.out.println("【测试用例3】偶数长度回文");System.out.println("子测试1：[1,2,2,1]");ListNode even1 = buildList(new int[]{1, 2, 2, 1});testAllMethods(even1, true);System.out.println("子测试2：[1,2,3,3,2,1]");ListNode even2 = buildList(new int[]{1, 2, 3, 3, 2, 1});testAllMethods(even2, true);System.out.println();}/*** 测试用例4：奇数长度回文*/public void testCase4_OddPalindrome() {System.out.println("【测试用例4】奇数长度回文");System.out.println("子测试1：[1,2,1]");ListNode odd1 = buildList(new int[]{1, 2, 1});testAllMethods(odd1, true);System.out.println("子测试2：[1,2,3,2,1]");ListNode odd2 = buildList(new int[]{1, 2, 3, 2, 1});testAllMethods(odd2, true);System.out.println();}/*** 测试用例5：非回文链表*/public void testCase5_NotPalindrome() {System.out.println("【测试用例5】非回文链表");System.out.println("子测试1：[1,2,3]");ListNode notPalin1 = buildList(new int[]{1, 2, 3});testAllMethods(notPalin1, false);System.out.println("子测试2：[1,2,3,4]");ListNode notPalin2 = buildList(new int[]{1, 2, 3, 4});testAllMethods(notPalin2, false);System.out.println("子测试3：[1,2,1,3]");ListNode notPalin3 = buildList(new int[]{1, 2, 1, 3});testAllMethods(notPalin3, false);System.out.println();}/*** 测试用例6：较大回文链表*/public void testCase6_LargePalindrome() {System.out.println("【测试用例6】较大回文链表");// 构造大回文链表 [1,2,3,4,5,4,3,2,1]int[] values = {1, 2, 3, 4, 5, 4, 3, 2, 1};ListNode large = buildList(values);System.out.println("链表: " + printList(large));testAllMethods(large, true);System.out.println();}/*** 测试用例7：性能测试*/public void testCase7_PerformanceTest() {System.out.println("【测试用例7】性能测试");// 构造大回文链表int size = 10000;int[] values = new int[size];for (int i = 0; i < size / 2; i++) {values[i] = i + 1;values[size - 1 - i] = i + 1;}ListNode largePalindrome = buildList(values);System.out.println("构造了" + size + "个节点的回文链表");// 性能测试long[] times = new long[4];String[] methods = {"数组法", "递归法", "栈法", "最优解法"};times[0] = testPerformance(() -> new Solution1().isPalindrome(copyList(largePalindrome)));times[1] = testPerformance(() -> new Solution2().isPalindrome(copyList(largePalindrome)));times[2] = testPerformance(() -> new Solution3().isPalindrome(copyList(largePalindrome)));times[3] = testPerformance(() -> new Solution4().isPalindrome(copyList(largePalindrome)));System.out.println("性能对比结果：");for (int i = 0; i < 4; i++) {System.out.println(methods[i] + ": " + times[i] + " 纳秒");}System.out.println();}// ===== 辅助方法 =====private void testAllMethods(ListNode head, boolean expected) {System.out.println("  原链表: " + printList(head));System.out.println("  期望结果: " + expected);boolean result1 = new Solution1().isPalindrome(copyList(head));boolean result2 = new Solution2().isPalindrome(copyList(head));boolean result3 = new Solution3().isPalindrome(copyList(head));boolean result4 = new Solution4().isPalindrome(copyList(head));System.out.println("  数组法: " + result1 + " " + (result1 == expected ? "✅" : "❌"));System.out.println("  递归法: " + result2 + " " + (result2 == expected ? "✅" : "❌"));System.out.println("  栈方法: " + result3 + " " + (result3 == expected ? "✅" : "❌"));System.out.println("  最优解: " + result4 + " " + (result4 == expected ? "✅" : "❌"));boolean allCorrect = (result1 == expected) && (result2 == expected) && (result3 == expected) && (result4 == expected);System.out.println("  综合结果: " + (allCorrect ? "✅ 全部正确" : "❌ 存在错误"));}private ListNode buildList(int[] values) {if (values == null || values.length == 0) {return null;}ListNode head = new ListNode(values[0]);ListNode curr = head;for (int i = 1; i < values.length; i++) {curr.next = new ListNode(values[i]);curr = curr.next;}return head;}private ListNode copyList(ListNode head) {if (head == null) return null;ListNode newHead = new ListNode(head.val);ListNode newCurr = newHead;ListNode curr = head.next;while (curr != null) {newCurr.next = new ListNode(curr.val);newCurr = newCurr.next;curr = curr.next;}return newHead;}private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");ListNode curr = head;while (curr != null) {sb.append(curr.val);if (curr.next != null) sb.append(", ");curr = curr.next;}sb.append("]");return sb.toString();}private long testPerformance(Runnable test) {long start = System.nanoTime();test.run();long end = System.nanoTime();return end - start;}@FunctionalInterfaceinterface TestFunction {boolean test();}private long testPerformance(TestFunction test) {long start = System.nanoTime();test.test();long end = System.nanoTime();return end - start;}
}

8. 常见错误与调试技巧

8.1 常见错误分析

错误1：快慢指针位置判断错误

// ❌ 错误：没有正确找到中点
public boolean isPalindrome(ListNode head) {ListNode slow = head;ListNode fast = head;// 错误的终止条件while (fast.next != null) {  // 应该是 fast != null && fast.next != nullslow = slow.next;fast = fast.next.next;}// ...
}// ✅ 正确：正确的快慢指针
while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;
}

错误2：反转链表后忘记处理奇偶长度

// ❌ 错误：没有考虑奇数长度链表的中间节点
ListNode secondHalf = reverseList(slow);// 直接比较，奇数长度时会包含中间节点// ✅ 正确：处理奇数长度的情况
if (fast != null) {  // 奇数长度，跳过中间节点slow = slow.next;
}
ListNode secondHalf = reverseList(slow);

错误3：递归法中前向指针处理错误

// ❌ 错误：前向指针移动时机错误
private boolean recursivelyCheck(ListNode currentNode) {if (currentNode != null) {frontPointer = frontPointer.next;  // 错误位置if (!recursivelyCheck(currentNode.next)) {return false;}if (currentNode.val != frontPointer.val) {return false;}}return true;
}// ✅ 正确：在比较后移动前向指针
if (currentNode.val != frontPointer.val) {return false;
}
frontPointer = frontPointer.next;  // 正确位置

8.2 调试技巧

技巧1：可视化链表状态

/*** 链表状态可视化工具*/
public class ListStateVisualizer {public static void visualizePalindromeCheck(ListNode head) {System.out.println("=== 回文检查可视化 ===");// 显示原始链表System.out.println("原始链表:");printListWithIndices(head);// 找中点过程visualizeFindMiddle(head);// 反转过程ListNode middle = findMiddle(head);visualizeReverse(middle);}private static void printListWithIndices(ListNode head) {if (head == null) {System.out.println("空链表");return;}// 打印索引ListNode curr = head;int index = 0;System.out.print("索引: ");while (curr != null) {System.out.printf("%-3d", index++);curr = curr.next;}System.out.println();// 打印值curr = head;System.out.print("值:   ");while (curr != null) {System.out.printf("%-3d", curr.val);curr = curr.next;}System.out.println();// 打印箭头curr = head;System.out.print("     ");while (curr != null && curr.next != null) {System.out.print(" ↓ ");curr = curr.next;}System.out.println();}private static void visualizeFindMiddle(ListNode head) {System.out.println("\n查找中点过程:");ListNode slow = head;ListNode fast = head;int step = 0;while (fast != null && fast.next != null) {System.out.println("步骤 " + (++step) + ":");System.out.println("  slow 指向位置: " + getNodePosition(head, slow) + " (值: " + slow.val + ")");System.out.println("  fast 指向位置: " + getNodePosition(head, fast) + " (值: " + fast.val + ")");slow = slow.next;fast = fast.next.next;}System.out.println("中点找到: 位置 " + getNodePosition(head, slow) + " (值: " + slow.val + ")");}private static void visualizeReverse(ListNode head) {System.out.println("\n反转链表过程:");System.out.println("反转前: " + printList(head));ListNode reversed = reverseListWithSteps(head);System.out.println("反转后: " + printList(reversed));}private static ListNode reverseListWithSteps(ListNode head) {ListNode prev = null;ListNode curr = head;int step = 0;while (curr != null) {System.out.println("反转步骤 " + (++step) + ":");System.out.println("  当前节点: " + curr.val);ListNode next = curr.next;curr.next = prev;System.out.println("  反转指针: " + curr.val + " -> " + (prev == null ? "null" : prev.val));prev = curr;curr = next;}return prev;}// 辅助方法private static int getNodePosition(ListNode head, ListNode target) {int pos = 0;ListNode curr = head;while (curr != null) {if (curr == target) return pos;curr = curr.next;pos++;}return -1;}private static ListNode findMiddle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private static String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");while (head != null) {sb.append(head.val);if (head.next != null) sb.append(" -> ");head = head.next;}sb.append("]");return sb.toString();}
}

技巧2：单步调试模式

/*** 单步调试工具*/
public class StepByStepDebugger {private Scanner scanner = new Scanner(System.in);public boolean debugPalindrome(ListNode head) {System.out.println("=== 单步调试模式 ===");System.out.println("按回车键继续每一步...");pause("开始检查回文链表: " + printList(head));if (head == null || head.next == null) {pause("边界条件：返回 true");return true;}// 第一步：找中点pause("第一步：使用快慢指针找中点");ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {pause("移动指针：slow=" + slow.val + ", fast=" + fast.val);slow = slow.next;fast = fast.next.next;}pause("找到中点：" + slow.val);// 第二步：反转后半部分pause("第二步：反转后半部分");ListNode secondHalf = reverseList(slow);pause("反转完成：" + printList(secondHalf));// 第三步：比较pause("第三步：比较前后两部分");ListNode firstHalf = head;boolean result = true;while (secondHalf != null) {pause("比较：" + firstHalf.val + " vs " + secondHalf.val);if (firstHalf.val != secondHalf.val) {pause("不相等！不是回文");result = false;break;}pause("相等，继续...");firstHalf = firstHalf.next;secondHalf = secondHalf.next;}pause("检查完成，结果：" + (result ? "是回文" : "不是回文"));return result;}private void pause(String message) {System.out.println(message);System.out.print("按回车继续...");scanner.nextLine();}private ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}private String printList(ListNode head) {if (head == null) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");while (head != null) {sb.append(head.val);if (head.next != null) sb.append(" -> ");head = head.next;}sb.append("]");return sb.toString();}
}

9. 算法复杂度对比与选择建议

9.1 四种解法对比表

解法	时间复杂度	空间复杂度	实现难度	是否满足进阶	推荐指数
数组法	O(n)	O(n)	⭐⭐	❌	⭐⭐⭐
递归法	O(n)	O(n)	⭐⭐⭐	❌	⭐⭐
栈方法	O(n)	O(n)	⭐⭐⭐	❌	⭐⭐⭐
最优解	O(n)	O(1)	⭐⭐⭐⭐	✅	⭐⭐⭐⭐⭐

9.2 选择建议

面试场景：

1. 初级面试：建议从数组法开始，展示思路清晰
2. 中级面试：展示栈方法，体现数据结构的灵活运用
3. 高级面试：直接实现最优解法，展示算法功底

实际应用：

1. 原型开发：使用数组法，快速实现功能
2. 生产环境：使用最优解法，考虑性能和内存
3. 教学演示：使用栈方法，便于理解回文特性

10. 总结与学习建议

10.1 核心要点总结

1. 算法理解：

   • 回文的本质是对称性
   • 链表的限制：单向访问、无随机访问
   • 空间与时间的权衡

2. 技巧掌握：

   • 快慢指针找中点
   • 链表反转操作
   • 递归回溯思想
   • 栈的LIFO特性应用

3. 复杂度分析：

   • 时间复杂度：所有解法都是O(n)
   • 空间复杂度：从O(n)到O(1)的优化过程
   • 满足进阶要求的重要性

10.2 学习建议

1. 循序渐进：

   • 先理解回文的概念
   • 掌握数组法的基本思路
   • 学习链表反转等基础操作
   • 最后挑战最优解法

2. 多练习：

   • 手动模拟执行过程
   • 画图理解指针移动
   • 编写测试用例验证
   • 尝试不同的边界条件

3. 深入理解：

   • 分析每种方法的适用场景
   • 理解空间复杂度优化的思路
   • 掌握链表操作的通用技巧

10.3 相关拓展题目

1. 回文判断系列：

   • 验证回文字符串
   • 回文数判断
   • 最长回文子串

2. 链表操作系列：

   • 反转链表
   • 合并两个有序链表
   • 环形链表检测
   • 链表的中间节点

3. 双指针技巧：

   • 两数之和
   • 三数之和
   • 快慢指针应用

10.4 面试准备要点

1. 基础扎实：

   • 熟练掌握链表节点的定义和基本操作
   • 理解快慢指针、反转链表等经典技巧
   • 能够分析时间和空间复杂度

2. 表达清晰：

   • 能够清楚地解释算法思路
   • 画图演示关键步骤
   • 分析不同解法的优缺点

3. 代码规范：

   • 处理边界条件
   • 变量命名清晰
   • 代码结构合理

回文链表是一道非常经典的链表题目，它综合考查了链表操作、指针技巧、空间优化等多个方面。通过深入学习这道题，你将掌握链表问题的核心解题思路和优化技巧！