描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。
你能给出空间复杂度的解法么？
输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

示例1：

输入：{3,2,0,-4},1
返回值：true

说明：
第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表 ,返回true  

示例2:

输入：{1},-1
返回值：false

说明：
第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false

示例:

输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：true

思路

如上图就是一个环形链表，他是有一个闭环的，他有一个特性：那就是如果顺着链表一直往前走，永远也走不到头。
这个特性一会证明链表是否有环的时候会用到。
咱们想想这么一个场景：在操场跑圈的时候，一个跑的快的人如果跑的时间够长最后会超过跑的慢的人。为啥那，因为操场是一个环形，没有尽头。所以如果一个链表如果是环形的，那么咱们可以找两个“运动员”去链表上跑一跑，也就是快慢指针，不就可以了。

public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        // 慢指针
        ListNode slow = head;
        // 快指针
        ListNode fast = head.next;
        // 如果fast == null 或 fast.next == null，说明有终点，就不是环形
        while (fast != null && fast.next != null) {
            // 当快慢指针相遇，说明快的追上了慢的，链表有环！！！
            if (slow == fast) {
                return true;
            }
            // 慢指针移动
            slow = slow.next;
            // 快指针移动
            fast = fast.next.next;
        }
        return false;
    }

时间复杂度：O(n),n 为链表长度
空间复杂度：O(1)

最后

这道题主要运用快慢指针的方式来解决的，其实很多题都是源于生活，只要咱们善于观察，相信自己也可以编写一道这样的经典题！
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。