🔗 回文链表

题目来源：234. 回文链表 – 力扣（LeetCode）

---

📌 题目描述

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

• 回文链表：链表从前往后读和从后往前读是一样的。
  例如：1 → 2 → 2 → 1 是回文，1 → 2 不是。

---

✅ 示例解析

示例 1：

• 输入：head = [1,2,2,1]
• 输出：true
• 解释：正读反读都是 1,2,2,1。

示例 2：

• 输入：head = [1,2]
• 输出：false
• 解释：正读是 1,2，反读是 2,1，不一致。

---

⚠️ 提示

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

---

💡 解法：快慢指针 + 反转后半部分 —— O(n) 时间，O(1) 空间

class Solution {
    // 辅助方法：反转链表
    public ListNode reverseList(ListNode head) {
        ListNode res = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = res;
            res = head;
            head = next;
        }
        return res;
    }

    // 主方法：判断是否为回文链表
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; // 空链表或单节点视为回文
        }

        // 1. 使用快慢指针找到后半部分的起始节点
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 2. 如果链表长度为奇数，slow 需要再前进一步（跳过中间节点）
        if (fast != null) {
            slow = slow.next;
        }

        // 3. 反转后半部分链表
        ListNode reversed = reverseList(slow);

        // 4. 比较前半部分与反转后的后半部分
        while (reversed != null) {
            if (reversed.val != head.val) {
                return false;
            }
            reversed = reversed.next;
            head = head.next;
        }

        return true;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 找中点：O(n/2)
  • 反转后半部分：O(n/2)
  • 比较两部分：O(n/2)
  • 总体为 O(n)
• 空间复杂度：O(1) ✅
  • 仅使用常数个额外指针，无递归或额外数组。

---

🧩 解题思路

1. 核心思想：比较前半部分与反转后的后半部分
   • 回文链表的特性是：前半部分 == 反转后的后半部分。
   • 因此，可以：
     1. 找到链表中点；
     2. 反转后半部分；
     3. 用两个指针分别从头和反转后的后半部分开始比较。
2. 步骤详解： 步骤 1：快慢指针找中点
   • fast 每次走两步，slow 每次走一步。
   • 当 fast 到达末尾时，slow 正好在中点。
   • 适用于偶数和奇数长度链表。
   步骤 2：处理奇数长度链表
   • 如果 fast != null，说明链表长度为奇数（因为 fast 走到了最后一个节点，未越界）。
   • 此时 slow 指向中间节点，应跳过它（slow = slow.next），因为中间节点不影响回文判断。
   步骤 3：反转后半部分
   • 调用 reverseList(slow) 得到反转后的后半部分链表。
   步骤 4：逐一对比
   • 用 head 从原链表头开始，reversed 从反转后的后半部分头开始。
   • 逐个比较 val，一旦不同立即返回 false。
   • 如果全部相同，返回 true。
3. 举例说明： 情况 1：偶数长度1→2→2→1
   • 找中点：slow 停在第二个 2（索引 2）
   • fast == null → 不跳过
   • 后半部分：2→1，反转后变为 1→2
   • 比较前半部分 1→2 与 1→2 → 相等 → true ✅
   情况 2：奇数长度1→2→3→2→1
   • slow 停在 3
   • fast != null → slow = slow.next → 指向第一个 2
   • 后半部分：2→1，反转后变为 1→2
   • 比较前半部分 1→2 与 1→2 → 相等 → true ✅
4. 边界处理：
   • 空链表：head == null → 返回 true。
   • 单节点：head.next == null → 返回 true。
   • 两个节点：slow 停在第二个节点，fast == null → 不跳过 → 反转第二个节点 → 比较。