你好！我是你的 NOI 竞赛金牌教练。今天我们要解析的是 LeetCode 的经典题目 Palindrome Linked List。虽然在 LeetCode 上它是以链表指针形式出现的，但在 NOI 竞赛中，这类题目通常考察的是序列处理逻辑以及对时空复杂度的极限优化。

一、 预备知识点

在解决此题前，你需要掌握以下核心考点：

1. 序列处理基础：双指针（Two Pointers）法。
2. 链表核心操作：
   • 快慢指针（Fast/Slow Pointers）定位中点。
   • 链表的原地反转（In-place Reversal）。
3. 时空复杂度权衡：
   • 基础解法：$O(n)$ 空间（转存数组）。
   • 进阶解法：$O(1)$ 额外空间（修改原结构）。
4. 递归思维：利用系统栈实现倒序遍历。

二、 题目描述 (NOI 风格)

题目名称：回文链表 (Palindrome Linked List) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个单链表的头节点 $head$，请判断该链表是否为回文链表。 所谓回文链表，是指链表中的元素从前向后读和从后向前读都是一样的。

注意：为了符合 NOI 竞赛对底层实现的考察，本题要求你在不使用额外 $O(n)$ 空间的前提下完成判断。

【输入格式】 第一行包含一个整数 $n$，表示链表的长度。 第二行包含 $n$ 个整数，表示链表中各节点的值。

【输出格式】 如果该链表是回文的，输出 1；否则输出 0。

【样例输入 1】

4
1 2 2 1

【样例输出 1】

1

【样例输入 2】

2
1 2

【样例输出 2】

0

【数据范围说明】

• $1 \le n \le 10^5$
• 节点权值 $0 \le val \le 9$
• 进阶要求：你能否用 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度解决此题？

三、 教学启发与思路引导 (草稿纸推演)

请在你的草稿纸上跟我一起画出这三个阶段的推理过程：

第一步：常规思路（空间 $O(n)$）

最简单的方法是将链表的值按顺序存入一个 std::vector。然后使用双指针 $L$ 和 $R$ 分别从两头向中间聚合，检查是否相等。 思考：NOI 考场上如果内存宽裕，这是最稳妥的保分写法。但如果内存极紧，我们需要更高级的做法。

第二步：寻找中点（快慢指针）

在草稿纸上画一个长度为 5 的链表。

• 让快指针一次走两步，慢指针一次走一步。
• 当快指针到达末尾时，慢指针恰好在中点。
• 这是一切链表结构优化题的基础技巧。

第三步：原地翻转与比较（空间 $O(1)$）

这是本题的“金牌解法”：

1. 使用快慢指针找到链表前半部分和后半部分的分界线。
2. 原地反转后半部分链表。
3. 同时从头节点和翻转后的后半部分起始节点开始比对。
4. 细节处理：比对完成后，建议将链表恢复原状（虽然在 LeetCode 判题中不是必须，但在工程实践和复杂的 NOI 模拟赛中是优良习惯）。

四、 算法流程图 (进阶版实现逻辑)

graph TD
    A(开始) --> B(快慢指针定位链表中点)
    B --> C(反转后半部分链表)
    C --> D(初始化 p1 指向头, p2 指向反转后的后半部分头)
    D --> E{p2 不为空吗}
    E -- 是 --> F{p1 和 p2 的值相等吗}
    F -- 否 --> G(返回 0 表示不是回文)
    F -- 是 --> H(p1 和 p2 同时后移)
    H --> E
    E -- 否 --> I(返回 1 表示是回文)
    G --> J(结束)
    I --> J

五、 时间与空间复杂度分析

1. 时间复杂度思考：

   • 寻找中点：遍历 $1/2$ 长度，$O(n)$。
   • 反转链表：遍历 $1/2$ 长度，$O(n)$。
   • 比较：遍历 $1/2$ 长度，$O(n)$。
   • 总计：$O(n)$。

2. 空间复杂度优化建议：

   • 暴力法：使用 vector 存储，空间 $O(n)$。
   • 优化法：直接在原链表节点上修改 next 指针，不使用额外容器。除了若干指针变量外，不随 $n$ 增加而消耗内存。
   • 最终评价：$O(1)$ 额外空间复杂度是该类题型的满分要求。

六、 总结：读题关键词与易错点

在竞赛中遇到“链表”和“回文”，请关注：

1. “恰好一半”的边界：当 $n$ 为奇数或偶数时，中点的位置可能略有不同。使用快慢指针时，要注意 fast->next 和 fast->next->next 的空指针检查。
2. 链表断开风险：在反转链表时，一定要用 temp 变量记录 next 节点，否则会造成链表丢失（Memory Leak）。
3. 节点修改：反转后的链表尾部通常指向 NULL，这可以作为比较时的终止条件。

教练点评：本题虽然是 LeetCode 原题，但在 NOI 中常通过“大模拟”或“动态内存管理”的形式包装。熟练掌握 $O(1)$ 空间复杂度的链表反转技巧，能让你在处理复杂数据结构时游刃有余。加油！