环形链表的双指针解法_链式成环 双指针

一、题目描述

二、解法

1.哈希表：哈希表边遍历存head边对比查找即可。

2.双指针：

1.首先确定是否存在环

        定义快慢指针初始化为头结点，快指针每次移动两个结点，慢指针每次移动一个头结点，若不存在环，则快慢指针永远不会相遇（慢指针追不上快指针），若存在环，则两者一定会相遇（进入环后，可以看成快指针追赶慢指针的过程，在这个追赶过程中，快指针相对慢指针每次多移动一个结点，不会存在跳过慢指针而不相遇的情况）。

2.确定环入口节点

假设头结点距离环口为x，慢指针进入环后再移动y个节点和快指针相遇（共移动了x+y个结点），此时快指针已经在环中移动了n圈，即移动的结点数为（x+n(y+z)+y)。

这里需要解释下为什么慢指针进入环后没走完一圈（小于等于一圈）必和快指针相遇，由于快指针每次移动结点数三十慢指针的两倍，假设慢指针进入环口时快指针正好走完n圈在环口处，情况如下图所示：

即加入快慢指针同时在环口开始移动，下次相遇必定在环口3处，此时慢指针走了一圈，快指针走了两圈，事实上，慢指针进入环口时，快指针更普遍的情况是在环中的某个位置：

 此时快指针追上慢指针（两者相遇时），慢指针一定还没移动完一圈。

其实可以理解成两个人（A速度快，B速度慢）环形跑道赛跑，若没有设置终点，则一直跑下去A一定会对B进行超圈。第一种情况对应AB同一起跑线开始，A对B超圈时B刚跑完一圈；那么将A的起跑线稍微往前拉一点，A对B的超圈一定发生在B还未跑完一圈时的情况。

解释完为什么慢指针未移动满一圈两者就会相遇，回到一开始对环入口的定位。已经说明了相遇时慢指针移动（x+y）个结点，快指针移动（x+n*(y+z)+y）个结点，而快指针移动速度时慢指针的两倍，此时：

2*(x+y) = x+n*(y+z)+y   =>   x+y = n*(y+z)  =>  x = (n - 1) (y + z) + z

当n=1时：x=z，表示快指针移动了一圈之后就和慢指针相遇了，此时头结点和相遇结点各定义一个指针并移动，相遇时即为环入口结点。

当n>1时：这两个指针相遇点仍为环入口，只不过此时相遇处定义的指针在环内多走了n-1圈。