234. 回文链表#

生活中的回文现象#

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

问题描述#

题目目标#

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

示例 1#

输入： 1 → 2 → 2 → 1 输出： true 链表示意：

输入:  1 -> 2 -> 2 -> 1 -> null
输出:  true

text

说明： 从左往右读和从右往左读都一样，所以这是一个回文链表。

示例 2#

输入： 1 → 2 → 3 → 2 → 1 输出： true 链表示意：

输入:  1 -> 2 -> 3 -> 2 -> 1 -> null
输出:  true

text

说明： 从左往右读和从右往左读都一样，所以这是一个回文链表。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

基础知识准备#

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

直观解法：转换为数组#

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

数组法实现#

public boolean isPalindrome(ListNode head) {
    // vals：按顺序保存链表节点值，便于后续双指针比较
    List<Integer> vals = new ArrayList<>();

    // current：遍历指针，从头到尾把节点值写入数组
    ListNode current = head;
    while (current != null) {
        // 收集当前节点值
        vals.add(current.val);
        // 继续遍历下一个节点
        current = current.next;
    }

    // left/right：数组两端指针，向中间收缩比较
    int left = 0, right = vals.size() - 1;
    while (left < right) {
        // 任一对不相等即可判定非回文
        if (!vals.get(left).equals(vals.get(right))) {
            return false;
        }
        // 两端指针向中间移动
        left++;
        right--;
    }

    // 全部对应位置都相等，说明是回文
    return true;
}

java

优化解法：反转后半部分#

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

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

这就像把一叠纸牌分成两半，把后半部分倒过来，然后一张张对比。

寻找中点：快慢指针法#

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

详细代码实现#

public boolean isPalindrome(ListNode head) {
    // 边界情况：空链表或单节点链表必然是回文
    if (head == null || head.next == null) {
        return true;
    }

    // 第1步：快慢指针找中点
    // slow 每次走一步，fast 每次走两步
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 第2步：从 slow.next 开始反转后半段
    // secondHalf 指向反转后半段的新头
    ListNode secondHalf = reverseList(slow.next);

    // 第3步：比较前半段与反转后的后半段
    // firstHalf 从头开始；secondHalf 从后半新头开始
    ListNode firstHalf = head;
    // temp：保存后半段头节点，供第4步恢复原链表使用
    ListNode temp = secondHalf;
    // result：默认是回文，若发现不等则置为 false
    boolean result = true;
    while (secondHalf != null) {
        // 逐节点比较值
        if (firstHalf.val != secondHalf.val) {
            result = false;
            break;
        }
        // 同步后移，继续比较下一对
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }

    // 第4步：把后半段再反转回来，恢复原链表结构
    slow.next = reverseList(temp);

    // 返回比较结果
    return result;
}

// 链表反转函数（使用我们之前学过的方法）
private ListNode reverseList(ListNode head) {
    // prev：已反转部分的头
    ListNode prev = null;
    // curr：当前待处理节点
    ListNode curr = head;
    while (curr != null) {
        // 暂存后继，防止指针改向后丢失链表
        ListNode nextTemp = curr.next;
        // 当前节点指向已反转部分
        curr.next = prev;
        // 前移 prev/curr，继续处理后续节点
        prev = curr;
        curr = nextTemp;
    }
    // prev 即反转后的新头
    return prev;
}

java

图解过程#

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

1) 初始状态：
1 → 2 → 3 → 2 → 1

2) 找到中点：
1 → 2 → [3] → 2 → 1
slow指向3

3) 反转后半部分：
1 → 2 → 3 ← 2 ← 1

4) 比较两半：
(1 → 2) 和 (1 → 2) 比较

5) 恢复原状：
1 → 2 → 3 → 2 → 1

plaintext

复杂度分析#

空间优化解法：

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

重要思维方式总结#

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

实用技巧总结#

解决类似问题的关键点：

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

小结#

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

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

下次遇到类似的对称性判断问题，不要急着用额外空间，想想是否可以通过改变数据结构本身来解决问题！