本文共 2406 字，大约阅读时间需要 8 分钟。

题目描述

给定一个链表，判断是否有环。

如下图，就是一个环形链表。

解法1：

你肯定很容易就能想到借助set集合的方式来实现，比如挨个遍历每个节点并放入set集合中，如果当前的节点在set集合中已经存在，则认为是环形链表，否则不是。

public class HasCycle {
       public static void main(String[] args) {
           ListNode head = new ListNode(1);        ListNode n1 = new ListNode(2);        ListNode n2 = new ListNode(3);        ListNode n3 = new ListNode(4);        ListNode n4 = new ListNode(5);        ListNode n5 = new ListNode(6);        ListNode n6 = new ListNode(7);        head.next = n1;        n1.next = n2;        n2.next = n3;        n3.next = n4;        n4.next = n5;        n5.next = n6;        //环形链表n6下一节点又指回了n2        n6.next = n2;        HasCycle c = new HasCycle();        System.out.println(c.hasCycle(head));    }    public boolean hasCycle(ListNode head) {
           Set
   
     nodeSet = new HashSet<>();        ListNode cur = head;        while (cur != null) {
               //如果set集合中已经存在当前节点，则调用add方法时会返回false            if (!nodeSet.add(cur)) {
                   return true;            }            cur = cur.next;        }        //一直遍历到最后，如果set都没重复添加过，则不是环形链表        return false;    }}
   

进阶要求

请你在O(1)空间复杂度内完成判定，也就是说不能再借助其他数据结构了。

解法2

快慢指针的方式，快指针每次走2步，慢指针每次走1步，如果是环形链表，那么快慢指针必定会相遇，如果不是那么快指针走到底就结束了。结论比较难证明，我们可以通过模拟验证。

假设有如下一个环形链表，我特意把它形象的画成了一个环形，依次按照慢指针走一步，快指针走两步的方式。

第一次

第二次

第三次

第四次

第五次

第六次，相遇

public class HasCycle {
       public static void main(String[] args) {
           ListNode head = new ListNode(1);        ListNode n1 = new ListNode(2);        ListNode n2 = new ListNode(3);        ListNode n3 = new ListNode(4);        ListNode n4 = new ListNode(5);        ListNode n5 = new ListNode(6);        ListNode n6 = new ListNode(7);        head.next = n1;        n1.next = n2;        n2.next = n3;        n3.next = n4;        n4.next = n5;        n5.next = n6;        //环形链表n6下一节点又指回了n2        n6.next = n2;        HasCycle c = new HasCycle();        System.out.println(c.hasCycle(head));    }    public boolean hasCycle(ListNode head) {
           //准备一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步        ListNode fastNode = head;        ListNode slowNode = head;        //如果快指针能走到null，则肯定不是环形链表，（环形链表是一个死循环）        while (fastNode != null && fastNode.next != null) {
               slowNode = slowNode.next;            fastNode = fastNode.next.next;            //如果相遇，则是环形链表            if (slowNode == fastNode) {
                   return true;            }        }        return false;    }}

转载地址：http://dhlrb.baihongyu.com/