1、快慢指针

1.1 算法的目标

判断链表中是否存在环形结构

1.2 算法的基本思想步骤

  1. 在每次移动中，快指针需要走 2 次，而慢指针需要走 1 次；
  1. 每次移动的步数等于数组中每个位置存储的元素；
  1. 当快慢指针相遇的时候，说明有环。

1.3 算法的具体流程：

1、这是快指针fast和慢指针slow，分别指向头节点（head节点），其中快指针每次移动2步，慢指针每次只移动一步：
2：快指针的走过链表末端，为空链表无环
3：快指针慢指针第一次相遇，说明该链表存在环，进一步确定环的入口位置：

     - 将快指针指向头节点
     - 再次移动快慢指针，快指针移动1步，慢指针移动1步
     - 循环，直到快慢指针第二次相遇，即找到环的入口

原理分析（步数分析）：
1、设链表共有 a+b个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b个节点，设快指针走了f步，慢指针走了s步。
2、根据两者对应关系可得到，f=2s；f=s+nb（n为环的圈数）
3、将以上两式相减，可以得到f=2nb，s=nb，即快指针和慢指针分别走了2n和n个环。
4、如果让指针从链表头部一直向前走并统计步数 k ，那么所有 走到链表入口节点时的步数 是：k = a + nb（先走 a 步到入口节点，之后每绕 1圈环（ b 步）都会再次到入口节点）。
5、而目前，slow 指针走过的步数为 nb 步。因此，我们只要想办法让 slow 再走 a步停下来，就可以到环的入口。但是我们不知道 a 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和 slow 一起向前走 a步后，两者在入口节点重合。那么从哪里走到入口节点需要 a步？答案是头节点！