1. 环形链表
众所周知，单链表是面试的常考点，假设你明天准备二面。由于时间不够了，你的链表基础也还行，所以你打算背两道题目，万一就考到了呢？于是你在链表题集中翻到了这道题。
链接：141. 环形链表
描述：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：pos 不作为参数进行传递 。仅仅 是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例2:：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
你一看题目，懵逼了。这带环链表可咋做啊！于是你翻开了力扣的答案册，看到了某个帅哥(假设是我)的题解。于是你打算看看。
思路(精讲)：
做这道题目之前我们需要明确一点 不能遍历链表 ，因为链表带环。
链表带环就是链表的某个节点中存储的地址为这个节点前的某个节点的地址。而导致闭环 ，使遍历链表时无法停止，走不到空，无法停止。
所以我们这道题目采用的方法是 快慢指针 。
总体思路是这样的，快指针走两步，慢指针走一步。给定快指针 fast ，慢指针 slow ，初始值为链表的头。
设入环前的距离为 x 。当 slow 走了 x/2 时，fast 入环。fast 走了一段路程后，slow 入环，fast 开始追击 slow，最后 fast 和 slow 相遇。
而这里面的走法，就和我们上篇博客中，求链表的中间节点的方法一样。奇数走到最后一个节点，偶数走到空。
如果走到这两个条件了，说明链表一定不带环。否则不会走到空，它们一定会相遇，为环形链表。
你一看思路，我去这么多！我就背个代码吧，反正到时候应该也就只考代码，我只要记住这个方法叫 快慢指针 就好了呗！
然后你背了两道题目后，准备睡觉。
2. 环形链表延伸问题
第二天，你进入了面试的房间。
你坐到面试官的对面。面试官笑嘻嘻地问你：“小伙子，环形链表 会吗”？然后笑眯眯地拿了一张纸给你，这张纸上恰好就是这道题。
你看到题目，心里十分兴奋，那不是我昨天背的题目吗！笑哈哈地说：“那可是我的拿手好戏！” 然后提笔唰唰唰地就把题目写完了。
面试官看了一眼，眉头一皱，嘴角一抿，然后恢复笑容，说：“那我考考你，你是怎么想到的呀？”
你一听，以为面试官不知道你的方法，然后自信地说：“ 快慢指针 ！”但是说完你后悔了，面试官问的是怎么想到的，这我咋会，我只会写，我说不出来呀…
面试官听到这里，好像察觉到了你内心的慌张，微微一笑，说：“那么你这么懂这个方法，那我问你几个问题吧！”
好了注意了，大家！接下来，请听题：
问题1：“为什么 slow 和 fast 指针一定会在环中相遇？会不会错过，永远追不上？请证明一下？”
听到这个问题，你内心一紧，表情略微苦涩。面试官观察到了你的表情，笑容越发嚣张，继续问：
问题2：“为什么 slow 走一步，fast 走两步？能不能 fast 一次走 n 步 (n > 2) ？请证明一下？”
你懵了，说：“我不会…。”
面试官笑着对你说：“小伙子，你还是太嫩了呀！想知道这是为啥吗？”
你十分憋屈地说：“不知道。您能讲讲吗？”
面试官歪嘴一笑：“说，想学啊？我教你啊！”
于是面试官就开始了他的表演，期间举止十分嚣张，一言一语透露着自信。
接下来不会的小伙伴听好了，面试官(也就是我，哎嘿)来为大家讲问题！
问题1：“为什么 slow 和 fast 指针一定会在环中相遇？会不会错过，永远追不上？请证明一下？”
第一步：slow 和 fast ，fast 一定是先进环。这时 slow 走了入环前距离的一半。
第二步：随着 slow 进环，fast 已经在环里走了一段了。走了多少跟环的大小有关。
假设 slow 进环时，slow 和 fast 的距离是 N。N 的长度一定小于环。
fast 开始追 slow ，slow 每次往前走 1 步，fast 往前走 2 步。每追一次，判断一下是否相遇。
每追 1 次，fast 和 slow 的距离变化：N -> N - 1 -> N - 2 … 1 -> 0.
每追 1 次，距离减少 1 。它们最后的距离减到 0 时，就是相遇点。
所以说，她逃他追，她插翅难飞。
额，不对，是快指针走两步一定会追到慢指针。
嗯对，接下来看下一个问题。
问题2：“为什么 slow 走一步，fast 走两步？能不能 fast 一次走 n 步 (n > 2) ？请证明一下？”
既然面试官这么问了，那么我们不妨走 n（n > 2） 步试一下。假设我们 slow 走一步，fast 走三步。
它们之间的 距离变化 如下：
| N 是偶数 | N 是奇数 |
| N | N |
| N - 2 | N - 2 |
| N - 4 | N - 4 |
| N - 6 | N - 6 |
| … | … |
| 2 | 1 |
| 0 | -1 |
| 可以追上 | 这一次追不上 |
注: N 是 fast 和 slow 之间的距离。
当 N 是 奇数 时，如果 fast 走 3 步， slow 走 1 步，一个周期是肯定追不上的。走到最后它们之间的距离变为 -1 ，意味着现在 fast 在 slow 前面一步，它们之间的距离变为 c - 1 。（c 是环的长度）
而长度一旦为 c-1 就有会引申出两种情况，看下图：
我们这里已经 初步证明 了当 fast 一次走 n(n > 2) 步时，fast 是不一定可以追上 slow 的。
举了一个 fast 走 奇数步 的例子，我们再举一个 fast 一次走 偶数步 的例子。
假设 fast 一次走 4 步，slow 一次走 1 步。
| N 是 3 的倍数 | N 不是 3 的倍数(N是 1 的倍数) | N 不是 3 的倍数(N 是 2 的倍数) |
| N | N | N |
| N - 3 | N - 3 | N - 3 |
| N - 6 | N - 6 | N - 6 |
| N - 9 | N - 9 | N - 9 |
| … | … | … |
| 3 | 2 | 1 |
| 0 | -1 | -2 |
| 可以追上 | 这一次追不上 | 这一次追不上 |
假设 c 是环的长度。
-1 意味着距离是 c - 1，-2 意味着距离是 c - 2。
如果 c - 1 和 c - 2 是 3 的倍数就可以追上，否则就追不上。
然后就可以以此类推，我就不多赘述了~
结论：fast 走 2 步，slow 一定可以追上，因为它们的距离逐次减 1 。但是当 n > 2 时，不一定会相遇。
随后面试官再次笑眯眯地问：“同学，你懂了吗？”
你说：“我懂了，请问帅气的面试官，可以再给我一次机会吗？”
面试官本来戏谑的笑容瞬间灿烂了起来，说：“其实我一眼看你就不简单啊哈哈！孺子可教也，那么我就再给你一次机会，这次你可要接好了！本道题目叫做：环形链表 II !
于是面试官带着笑容开始介绍起了题目~
