在数据结构的世界里，链表（Linked List）是一种非常特殊的线性结构。与数组不同，链表不支持随机访问，我们无法在 O(1) 的时间内直接获取第 k 个元素。这种限制使得链表题目往往成为考察对“空间复杂度”和“指针操作”理解深度的试金石。
今天我们通过三道经典的 LeetCode 题目——回文链表、环形链表及其入环节点检测，来深入探讨一种在链表中极其强大的算法思想：快慢指针（Fast & Slow Pointers）。这三道题的本质，都是通过利用两个指针移动速度或起始位置的差异，在不使用额外空间的情况下，挖掘出链表的结构特征。
一、 回文链表：空间复杂度的极致优化
题目：判断一个链表是否为回文链表。
1. 朴素解法 vs 优化解法
最直观的思路是将链表的值复制到一个数组中，利用数组的双指针从两端向中间判断。这虽然简单，但需要 O(N) 的空间复杂度。如果限制空间复杂度为 O(1) 呢？
这就要求我们在链表原地进行操作。我们需要解决两个痛点：
找到链表的中间节点。
链表是单向的，无法从后往前遍历。
2. 代码深度解析
你的代码采用了**“快慢指针找中点 + 反转后半部分”**的策略，这是一种破坏性（会修改原链表结构）但空间最优的解法。
C++代码实现：
class Solution { public: bool isPalindrome(ListNode* head) { // 步骤1：快慢指针找中点 // fast 走两步，slow 走一步。当 fast 到达终点时，slow 正好位于中点。 ListNode* slow = head; ListNode* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } // 步骤2：反转后半部分链表 // 此时 slow 指向后半部分的起始点 ListNode* pre = nullptr; ListNode* cur = slow; while (cur) { ListNode* nxt = cur->next; cur->next = pre; // 经典的指针转向操作 pre = cur; cur = nxt; } // 步骤3：双指针比对 // pre 指向反转后的尾节点（即现在的后半段头），head 指向原链表头 while (pre) { if (pre->val != head->val) return false; pre = pre->next; head = head->next; } return true; } };3. 本质与时空分析
本质：利用快指针是慢指针速度的 2 倍这一数学关系，一次遍历即可精准定位中点。反转链表则是为了克服单向链表无法回溯的缺陷。
时间复杂度：O(N)。找中点遍历 N/2，反转遍历 N/2，比对遍历 N/2，总操作仍为线性。
空间复杂度：O(1)。我们只利用了有限的几个指针变量，未申请额外内存，这是本题的优化核心。
二、 环形链表：追及问题的代码投射
题目：判断链表中是否有环。
1. 算法思想：弗洛伊德判圈算法
如果我们用一个哈希表存储走过的节点，一旦遇到重复的节点即为有环，但空间复杂度为 O(N)。 在 O(1) 空间下，我们将问题抽象为**“操场跑圈”模型：在一个环形跑道上，两个速度不同的人跑步，跑得快的人一定会套圈**（追上）跑得慢的人。
2. 代码深度解析
C++代码实现：
class Solution { public: bool hasCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; // 边界条件：只要 fast 还能走，说明没到尽头 while(fast && fast->next) { fast = fast->next->next; // 速度为 2 slow = slow->next; // 速度为 1 if(fast == slow) return true; // 相遇即有环 } return false; // 走到 nullptr 说明是直线，无环 } };3. 本质与时空分析
本质：相对速度。如果将 slow 看作静止，fast 实际上是以 1 的速度在向 slow 靠近。只要有环，它们之间的距离就会不断缩小，直至为 0。
时间复杂度：O(N)。如果有环，快指针在环内绕圈的次数不会超过环的长度即可追上慢指针。
空间复杂度：O(1)。
三、 环形链表 II：从相遇到入口的数学推导
题目：如果链表有环，找出环的入口节点。
1. 难点分析
上一题我们只判断了“有无”，这一题要求“在哪”。这是一个典型的数学问题。仅仅知道相遇点是不够的，我们需要推导出相遇点与入口点之间的位移关系。
2. 数学证明（深度核心）
假设：
链表头到环入口的距离为a。
环入口到相遇点的距离为b。
环的剩余长度（相遇点回到入口）为c。
快指针在环里转了n圈。
推导过程：
慢指针走的距离：
distance_slow = a + b快指针走的距离：
distance_fast = a + b + n(b + c)因为快指针速度是慢指针的 2 倍，所以：
2(a + b) = a + b + n(b + c)化简得：
a + b = n(b + c)=>a = n(b + c) - b进一步整理：
a = (n - 1)(b + c) + c
结论：当 n=1 时（通常第一次相遇时 n 就是 1），公式简化为a = c。 这意味着：从链表头出发一个指针，同时从相遇点出发一个指针，它们每次走一步，最终一定会在环的入口处相遇。
3. 代码深度解析
C++代码实现：
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; // 第一阶段：判断是否有环并找到相遇点 if (fast == slow) { // 第二阶段：数学魔法生效 // head 从起点出发，slow 从相遇点出发 // 根据 a = c，它们走过相同的距离后必在入口相遇 while(head != slow) { slow = slow->next; head = head->next; } return slow; // 返回入口节点 } } return NULL; } };4. 本质与时空分析
本质：利用快慢指针的行程差构建等式，将几何距离转化为代数关系。
时间复杂度：O(N)。看似有两个循环，但总体指针移动次数与链表长度成线性关系。
空间复杂度：O(1)。
总结
这三道题目展示了链表算法优化的核心方向：用计算换空间。
回文链表：通过指针计算找到中点，用局部反转代替全量复制。
环形链表：通过相对速度判断闭环，避免了哈希表的空间开销。
入环节点：通过严格的数学推导，将指针的相遇位置转化为链表的结构坐标。
掌握快慢指针，加理解如何在受限的数据结构（如单向链表）中，通过增加“维度”（指针的速度和数量）来获取全局信息的能力。
