[链表]3.判断给定的链表中是否有环 扩展： 你能给出空间复杂度O(1)的解法么？[网易互娱，中国移动考过]

码字不易，记得点赞加收藏

题目：.判断给定的链表中是否有环 扩展： 你能给出空间复杂度O(1)的解法么

知识点：快慢指针

1.快慢指针的妙用

我们先来简单介绍一下何为快慢指针。快慢指针就是定义两根指针，移动的速度一快一慢，以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。

如果现在对这里的简介不是很理解，没有关系，我们一起来看看如下的几个例子。相信看完后，就会明白了。

1.1 找中间值

一般的思路是：先遍历一次链表，记录住一共有多少个节点，然后，再次遍历找寻中点。

利用快慢指针，我们来看看这个问题会变成什么样。思路如下：我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。

如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。

1.2 判断链表中的环

还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环。

为了不失一般性，我们在环上加了额外的两个节点，我们可以想象一下，只要两个指针跑进了环里，那么因为存在速度差，他们之间的距离总会由远及近，然后相遇，在远离。像极了我们人世间某些人在你生命中匆匆而过的感觉。

代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //解法1.快慢指针
        if(head == null)return false;
        //定义快慢指针
        ListNode fastNode = head;
        ListNode slowNode = head;
         while(fastNode !=null && fastNode.next!=null){
             fastNode = fastNode.next.next;
             slowNode = slowNode.next;
             if(fastNode == slowNode){
                 return true;
             }
         }
        return false;  
    }
}