[Algorithm] 双指针应用

双指针应用

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

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 imes C ightarrow K=N imes C ]

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

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

[S = K-NS imes C - L=2K-NF imes C - L ]

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

[C-S=(C-K+NS imes C+L)mod(C) =((1-N+NS) imes 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;
    }
};