链接

Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

**![image.png](https://cdn.nlark.com/yuque/0/2020/png/334665/1585842471270-7dc99b0b-9e3b-4d78-a866-70866817fd9b.png#align=left&display=inline&height=630&name=image.png&originHeight=721&originWidth=810&size=47572&status=done&style=none&width=707)**

Follow up:
Can you solve it using O(1) (i.e. constant) memory?

这道题是快慢指针的经典应用。只需要设两个指针，一个每次走一步的慢指针和一个每次走两步的快指针，如果链表里有环的话，两个指针最终肯定会相遇。实在是太巧妙了，要是我肯定想不出来。代码如下：

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         ListNode slow = head, fast = head;
  4.         while (fast != null && fast.next != null) {
  5.             slow = slow.next;
  6.             fast = fast.next.next;
  7.             if (slow == fast) return true;
  8.         }
  9.         return false;
  10.     }
  11. }

拓展

由此，可以拓展出一些相关的问题来：

  1. 环的长度是多少？

  2. 如何找到环中第一个节点（即Linked List Cycle II）？

  3. 如何将有环的链表变成单链表（解除环）？

首先可以看下面这张图：
image.png

其中，X是起点，Y是环的交叉点，Z是快慢指针的相遇点，a、b、c表示相应的线段长度。

接下来逐个问题来分析一遍：

  1. 环的长度是多少？

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

  1. 如何找到环中第一个节点（即Linked List Cycle II）？

我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

  1. 如何将有环的链表变成单链表（解除环）？

在上个问题的基础上，将Y结点的next置为NULL即可。