当前位置：首页 > news >正文

从零开始写算法——链表篇2:从“回文”到“环形”——链表双指针技巧的深度解析

news 2026/5/11 20:52:07

在数据结构的世界里，链表（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; } };