一、快慢指针原理

快慢指针示意图

1、一般步骤

  • Step1:从起点A开始，快指针每次走两步，慢指针每次走一步；当两个指针相遇时（假设相遇点为C）下一步。
  • Step2:再从起点A开始，设立一个慢指针，两个慢指针一起每次走一步；两个慢指针相遇的位置就是环入口B。

2、原理分析

1、假设A到B距离为a，B到C距离为b，C到B距离为c（顺时针）。
2、快慢指针相遇时，两个指针走过的距离及关系

  • 快指针：a+m(b+c)+b，m圈
  • 慢指针：a+n(b+c)+b，n圈
  • 快指针每次走2步，慢指针每次走1步，所以有：a+m(b+c)+b=2[a+n(b+c)+b]，得到a+b=(m-2n)(b+c) (1)式。
  • 当慢指针第一次到达B时，快指针已经在环上走了k圈了，慢指针在环上走了n圈，所以快指针又走了2n圈，得到m-2n=k (2)式。
  • (2)代入(1)得到a=(k-1)(b+c)+c，所以当慢指针1从A走a步到达B时，慢指针2正好从C走k-1圈+c步到达B，即正好相遇在B点。

二、例题：寻找重复数（来源：LeetCode）

 public static int findDuplicate(int[] nums) {
     // 快慢指针从起点开始，快指针每次走2步，慢指针每次走1步，找到在环中相遇位置
     int tortoise = nums[0];
     int hare = nums[0];
     do {
         tortoise = nums[tortoise];
         hare = nums[nums[hare]];
     }
     while (tortoise != hare);

     // 慢指针从相遇位置继续走，再加一个慢指针从起点开始，两个慢指针相遇的位置就是环的入口
     int ptr1 = nums[0];
     int ptr2 = tortoise;
     while (ptr1 != ptr2) {
         ptr1 = nums[ptr1];
         ptr2 = nums[ptr2];
     }
     return ptr1;
 }