环形链表是链表中的一类特殊问题，它和链表反转一样，有着相对恒定的解题思路和适当的变体。如果你对它的特性和解法没有预先的了解和把握，那么前期的推导可能会花去你大量的时间。反过来看，只要我们能够掌握其核心思路，那么不管它怎么变化，大家都能在瞬间找到解题的“抓手”、进而给出正确的解答。

环形链表基本问题——如何判断链表是否成环？

⚡ 30 秒速记

• 不修改链表时首选 Floyd 快慢指针：slow 每次一步，fast 每次两步。
• 有环时快指针会在环内追上慢指针；无环时 fast 或 fast.next 先到 null。
• 时间 O(n)、额外空间 O(1)；Set 法更直观但空间为 O(n)。
• 循环条件先保护 fast && fast.next，比较的是节点引用而不是节点值。

不修改链表的情况下，我一般用 Floyd 快慢指针判断是否有环。 slow 每轮走一步，fast 每轮走两步；进入有限长度的环后，快指针会不断缩短与慢指针的相对距离，最终相遇。若 fast 或 fast.next 先变成 null，则说明没有环；实现时比较节点引用而不是节点值，时间为 O(n)、额外空间为 O(1)。

回答参考：“我先确认不能修改节点。然后用 Floyd 判环：快慢指针进入有限长度的环后，相对位置每轮前进一格，所以必然相遇；若快指针抵达 null，则无环。”

真题描述：给定一个链表，判断链表中是否有环。

示例 1：

输入：[3,2,0,4]（链表结构如下图） 输出：true

解释：链表中存在一个环

思路解读

其实链表成环的特征非常明显，大家可以结合一个现实中的例子来理解：

假如现实中有一个长跑爱好者李雷，这货很狂，他立了一个 flag，说要徒步环游世界：

地球的周长围出来的这个圆，它就是一个“环”。李雷现在就想围着这个环跑上一圈，说他狂，他也没那么狂——他觉得自己最多跑一圈，为了防止自己跑过界，他决定在出发的地方立一个 flag：

这样，不管李雷走完这个环用了多少年，世事如何变迁，只要他的 flag 还没有倒，那么李雷就一定能回到自己梦开始的地方：）。

换个角度看：只要李雷在闷头前进的过程中，发现了 flag 的存在，那么就意味着，李雷确实走了一个环。毕竟若这是一条线，他将永远无法回到起点。

回到链表的世界里，也是一个道理。一个环形链表的基本修养，是能够让遍历它的游标回到原点

从 flag 出发，只要我能够再回到 flag 处，那么就意味着，我正在遍历一个环形链表。

我们按照这个思路来做题：

编码实现

/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 入参是头结点 
const hasCycle = function(head) {
    // 只要结点存在，那么就继续遍历
    while(head){
        // 如果 flag 已经立过了，那么说明环存在
        if(head.flag){
            return true;
        }else{
            // 如果 flag 没立过，就立一个 flag 再往
            下走
            head.flag = true;
            head = head.next;
        }
    }
    return false;
};