返回文章列表

快慢指针

2026年3月28日4 分钟阅读

算法进阶：彻底搞懂“快慢指针”及其妙用

在处理链表（Linked List）或循环数组问题时，传统的单指针遍历往往显得力不从心。今天我们要聊的 快慢指针（Fast & Slow Pointers），通过“步频差异”这一巧妙设计，能优雅地解决许多看似复杂的时间与空间复杂度挑战。

1. 什么是快慢指针？

顾名思义，我们同时使用两个指针在数据结构上移动：

  • 慢指针 (Slow)：每次向前移动 1 个步长。
  • 快指针 (Fast)：每次向前移动 2 个（或更多）步长。

这种步频差就像“龟兔赛跑”，只要路程足够长或存在环路，快指针一定会与慢指针产生特定的相对位置关系，从而帮助我们推导出结构的特征。

2. 核心应用场景

① 判定链表是否有环 (Floyd's Cycle-Finding Algorithm)

这是快慢指针最经典的应用，也被称为“龟兔赛跑算法”。

  • 逻辑：如果链表中存在环，快指针最终会进入环并在某个时刻“套圈”慢指针，两者在环内相遇。
  • 优势：空间复杂度仅为 O(1)，不需要额外的哈希表存储访问记录，极大地节省了内存。

② 寻找链表的中点

在不预先知道链表长度的情况下，如何仅通过一次遍历找到中点？

  • 逻辑：快指针的速度是慢指针的两倍。当快指针到达链表末尾（null）时，慢指针刚好走到了全长的一半。
  • 用途：常用于链表的归并排序（Merge Sort）或判断回文链表。

③ 寻找环的入口点

这是一个进阶的数学问题。

  • 逻辑：在快慢指针第一次相遇后，将其中一个指针放回起点（Head），两个指针现在以相同速度（步长皆为 1）同时前进。当它们再次相遇时，相遇点即为环的入口。

3. 代码演示 (C语言实现)

  • 判断链表是否有环
  • 返回 1 表示有环，返回 0 表示无环
int isCycle(Node *head) 
{
   Node *fast = head;
   Node *slow = head;

   while (fast != NULL && fast->next != NULL)   //这里的while循环条件是fast指针和fast指针的下一个节点都不为NULL,确保fast指针不会越界.
   {
       fast = fast->next->next; // 快指针每次走两步
       slow = slow->next;        // 慢指针每次走一步

       if (fast == slow)        // 快慢指针相遇，说明有环
       {
           return 1;
       }
   }

   return 0; // 快指针走到尽头，说明无环
}
  • 找到链表环的入口
  • 返回环的起始节点指针
Node* findBegin(Node *head)
{
   Node *fast = head;
   Node *slow = head;

   // 第一步：利用快慢指针判断是否有环
   while (fast != NULL && fast->next != NULL)
   {
       fast = fast->next->next;
       slow = slow->next;

       // 如果相遇，说明有环
       if (fast == slow)
       {
           // 第二步：计算环中节点的个数 count
           Node *p = fast;
           int count = 1;
           while (p->next != slow)
           {
               count++;
               p = p->next;
           }

           // 第三步：寻找环的入口
           fast = head;
           slow = head;

           // 让 fast 指针先走 count 步
           for (int i = 0; i < count; i++)
           {
               fast = fast->next;
           }

           // 然后 fast 和 slow 同步前进，相遇点即为入口
           while (fast != slow)
           {
               fast = fast->next;
               slow = slow->next;
           }
           
           return slow;
       }
   }

   return NULL; // 无环
}

4. 为什么这个技巧很重要？

  • 极高的空间效率：它能将原本需要 O(n) 空间的算法（例如使用哈希表或集合来记录已访问节点）降低到 O(1) 的常数级空间。
  • 打破思维定式：它提醒我们，遍历数据结构时不一定只有一种速度。通过制造“速度差”，我们可以巧妙地挖掘出链表或数组中隐藏的几何属性（如中点、环路等）。

结语

快慢指针是算法面试中的“常客”，也是提升程序效率的利器。下次当你看到链表、循环或需要寻找特定比例位置的问题时，不妨停下来想想：是不是可以让其中一个指针“跑快点”？

发表评论