✅ 最优解法：快慢指针 + 反转后半部分（空间 O(1)）
目标：不使用额外数组/栈，仅用 O(1) 空间完成。
🧠 思路分三步：
- 用快慢指针找到链表中点
- 反转后半部分链表
- 比较前半部分和反转后的后半部分是否相同
- （可选）恢复链表原状
💡 Java 实现（带恢复链表）
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// Step 1: 找到前半部分的尾节点（使用快慢指针）
ListNode firstHalfEnd = endOfFirstHalf(head);
// Step 2: 反转后半部分
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// Step 3: 比较前半部分和反转后的后半部分
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// Step 4: 恢复链表（可选，但推荐保持输入不变）
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
// 快慢指针找前半部分结尾
private ListNode endOfFirstHalf(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // 奇数长度时，slow 在中间；偶数时在前半最后一个
}
// 反转链表
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
🔍 示例说明
输入：1 -> 2 -> 2 -> 1
- 快慢指针：
slow停在第一个2（前半结尾） - 反转后半：
1 -> 2 -> null←2 <- 1 - 比较：
1==1,2==2→ 回文 ✅
输入：1 -> 2 -> 3 -> 2 -> 1
slow停在3（中间）- 反转后半：
1 -> 2 -> 3 -> null←2 <- 1 - 比较：
1==1,2==2→ 回文 ✅
⏱️ 复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(n)（遍历 2~3 次链表） |
| 空间复杂度 | O(1)（只用几个指针） |
✅ 完全满足“不使用额外空间”的要求（对比：用栈或数组需要 O(n) 空间）
❌ 其他方法对比
| 方法 | 时间 | 空间 | 缺点 |
|---|---|---|---|
| 转数组 + 双指针 | O(n) | O(n) | 需要额外存储 |
| 递归 + 全局指针 | O(n) | O(n) | 递归栈深度 O(n) |
| 快慢指针 + 反转 | O(n) | O(1) | 最优解 |
✅ 总结
- 面试高频题，必须掌握 O(1) 空间解法。
- 关键技巧：快慢指针找中点 + 链表反转。
- 如果题目不要求恢复链表，可以省略最后一步（但最好加上，体现工程素养）。