【LeetCode 刷题】回文链表：O (1) 空间最优解（快慢指针 + 反转链表）

判断链表是否为回文链表是链表类高频面试题，常规解法（如转数组对比）会占用 O (n) 空间，而本文分享的「快慢指针找中点 + 反转后半段链表」解法，能在 O (n) 时间、O (1) 空间 内完成判断，是面试中最亮眼的最优解。

一、题目描述

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

核心定义

回文链表：正序遍历和逆序遍历的节点值完全一致，例如：

• 有效回文：1 -> 2 -> 2 -> 1、1 -> 3 -> 5 -> 3 -> 1
• 无效回文：1 -> 2 -> 3、1 -> 2 -> 1 -> 3

链表节点定义

java

运行

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */

二、解题思路：核心三步法

核心原理

回文的本质是「前半段 = 后半段的反转」，因此最优解的思路是：

1. 找中点：用快慢指针找到链表中点，将链表拆分为「前半段」和「后半段」；
2. 反转后半段：反转后半段链表，使其与前半段方向一致；
3. 对比两段：遍历前半段和反转后的后半段，节点值全部相等则为回文。

关键细节（快慢指针找中点）

• 慢指针（slow）：每次走 1 步，最终停在前半段最后一个节点；
• 快指针（fast）：每次走 2 步，用于确定中点位置；
• 初始值：fast = head.next（而非 head），目的是让 slow 停在前半段最后一个节点（避免奇数长度时后半段包含中间节点）。

思路可视化（以 1->2->2->1 为例）

plaintext

1. 找中点：
   slow=1 → 2（停在前半段最后一个节点），fast=2 → null（循环结束）
   前半段：1->2，后半段：2->1

2. 反转后半段：
   后半段 2->1 反转后变为 1->2

3. 对比两段：
   前半段 1->2 vs 反转后后半段 1->2 → 全部相等，返回 true

三、完整代码实现

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 边界条件：空链表或单节点链表直接是回文
        if (head == null || head.next == null) {
            return true;
        }

        // 慢指针：最终指向前半段最后一个节点
        ListNode slow = head;
        // 快指针：步长2，用于找链表中点
        ListNode fast = head.next;
        
        // 快慢指针找中点：fast走到末尾时，slow停在前半段最后一个节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转后半段链表
        ListNode reversedSecondHalfHead = reverse(slow.next);
        // 断开前半段和后半段的连接，避免对比时越界
        slow.next = null;

        // 遍历反转后的后半段，对比前半段节点值
        while (reversedSecondHalfHead != null) {
            if (reversedSecondHalfHead.val != head.val) {
                return false;
            }
            reversedSecondHalfHead = reversedSecondHalfHead.next;
            head = head.next;
        }
        
        return true;
    }

    /**
     * 反转单链表（迭代实现，O(1) 空间）
     * @param listHead 待反转的链表头节点
     * @return 反转后的链表头节点
     */
    public ListNode reverse(ListNode listHead) {
        ListNode prev = null;    // 前驱节点
        ListNode current = listHead; // 当前节点
        
        while (current != null) {
            ListNode tempNext = current.next; // 暂存下一个节点，避免链表断裂
            current.next = prev;              // 反转当前节点的指向
            prev = current;                   // 前驱节点后移
            current = tempNext;               // 当前节点后移
        }
        
        return prev; // 反转后的新头节点
    }
}