力扣 234. 回文链表

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

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

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

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

题目解读

回文链表：本质是单链表的一种特殊结构 —— 从链表头部到尾部遍历得到的节点值序列，和从尾部到头部遍历得到的序列完全一致，比如 "abba"、"12321"，正读和反读都相同。我们往往使用这'对称性'解决问题。

思路一

将链表转换为数组后使用双指针判断是否是回文。

具体步骤与解析

1. 统计链表长度

int len = 0; // 用以储存链表长度
ListNode cur = head; // 从头节点出发
while (cur != null) {
    len++; // 每遍历一个节点，长度 +1
    cur = cur.next; // 游标后移
}

作用：确定后续数组的长度，避免数组越界或浪费空间。

2. 将链表值存入数组

cur = head; // 重置游标，回到链表头
int[] res = new int[len]; // 根据长度创建数组
for (int i = 0; i < res.length; i++) {
    res[i] = cur.val; // 存入当前节点值
    cur = cur.next; // 游标后移
}

注意：这里 for 循环的终止条件是 i < res.length，和链表长度完全匹配，不会遗漏或越界。

3. 双指针判断回文

for (int i = 0, j = len - 1; i < j; i++, j--) {
    if (res[i] != res[j]) { // 对称位置值不等，直接返回 false
        return false;
    }
}
return true; // 所有对称位置相等，是回文

左指针 i 从数组头部（i=0）开始，右指针 j 从数组尾部（j=len-1）开始，只要有一对值不相等，直接返回 false；反之若循环结束（i >= j）都未发现不相等，返回 true。

核心思路总结

先统计长度→再存值到数组→双指针判回文。

完整代码

class Solution {
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        cur = head;
        int[] res = new int[len];
        for (int i = 0; i < res.length; i++) {
            res[i] = cur.val;
            cur = cur.next;
        }
        for (int i = 0, j = len - 1; i < j; i++, j--) {
            if (res[i] != res[j]) {
                return false;
            }
        }
        return true;
    }
}

思路二

先使用快慢指针找到链表中点将链表分为两个部分，再将后部分链表反转与前部分一一对应来判断回文链表。

具体步骤与解析

1. 处理边界情况

if (head == null || head.next == null) return true;

空链表 或 只有 1 个节点的链表，本身就是回文，直接返回 true。

2. 快慢指针找链表中点

while (fast != null && fast.next != null) {
    pre = slow; // 记录 slow 的前一个节点（分割点）
    slow = slow.next; // 慢指针走 1 步
    fast = fast.next.next; // 快指针走 2 步
}

慢指针（slow）每次走 1 步，快指针（fast）每次走 2 步，当 fast 走到链表末尾时，slow 恰好走到链表后半段的起点，pre 始终记录 slow 的前一个节点，用于后续分割链表。

3. 分割链表 + 反转后半段

pre.next = null; // 切断前半段和后半段的连接
// 前半段链表的头
ListNode cur1 = head;
// 反转后半段链表，得到反转后的头
ListNode cur2 = reverseList(slow);

辅助方法（reverseList）

ListNode reverseList(ListNode head) {
    ListNode tmp = null; // 临时存储下一个节点
    ListNode pre = null; // 记录当前节点的前一个节点
    while (head != null) {
        tmp = head.next; // 先保存下一个节点，避免断链
        head.next = pre; // 当前节点指向前一个节点（反转）
        pre = head; // pre 后移到当前节点
        head = tmp; // head 后移到原本的下一个节点
    }
    return pre; // 反转后的链表头
}

4. 对比前后两段链表

while (cur1 != null) {
    if (cur1.val != cur2.val) {
        return false;
    }
    cur1 = cur1.next;
    cur2 = cur2.next;
}
return true;

逐一比较两个链表的节点，值只要有一个值不相等，就不是回文；全部相等则是回文。

完整代码

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = null; }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode cur1 = head;
        ListNode cur2 = reverseList(slow);
        while (cur1 != null) {
            if (cur1.val != cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }
    
    ListNode reverseList(ListNode head) {
        ListNode tmp = null;
        ListNode pre = null;
        while (head != null) {
            tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
}