双指针应用

常见的双指针算法应用有：

1. 去除链表倒数第 N 个数

   # Remove Nth Node From End of List

2. 寻找链表中的环

   # Linked List Cycle

   # Linked List Cycle II

   # Find the Duplicate Number

双指针寻找环：

假设环的长度为$C$, 令快指针是慢指针的两倍速，都从 head 开始出发，慢指针步数为$K$ 时两节点相遇，则此时快指针步数为$2K$

设 head 距离环入口的长度为 L, 则：

$$2K - K = N\times C \rightarrow K=N\times C$$

其中 N 为快慢指针相差的圈数

则相遇的节点距离入口的长度为：

$$S = K-NS\times C - L=2K-NF\times C - L$$

其中 NS 为慢指针的圈数，NF 为快指针的圈数

$$C-S=(C-K+NS\times C+L)mod(C) =((1-N+NS)\times C+L)mod(C)=L$$

因此只要再走 L 步则可以到达圈入口点

则将快指针重新置为 head , 与慢指针同速开始走，相遇的节点即为入口

代码实现参考 Find the Duplicate Number

class Solution {

public:

    int findDuplicate(vector<int> &nums)

    {

        int slow = nums[0], fast = nums[slow];

        while (fast != slow)

        {

            fast = nums[nums[fast]];

            slow = nums[slow];

        }

        fast = 0;

        while (fast!=slow){

            fast = nums[fast];

            slow = nums[slow];

        }

        return slow;

    }

};