单向链表的闭环判断

单向链表，只能访问next元素，如何判断是否存在环？

 

最简单的方案，不考虑空间复杂度，我们会想到使用一个Set来保存集合，用来记录已经访问过的元素…

/**
     * 最简单的算法，但需要的空间比较高，一个Set集合
     * @param link
     * @param <T>
     * @return
     */
    public static <T>  boolean containsCircle1(Link<T> link) {
        if(link == null){
            return false;
        }
        T value = link.getValue();
        Set<T> values = new HashSet<T>();
        values.add(value);
        while ((link = link.getNext()) != null){
            if(link == null){
                return false;
            }
            value = link.getValue();
            if (values.contains(value)) {
                return true;
            }
        }
        return false;
    }

 

 

这会浪费O(n)的空间，效率低下，如果链表长度过长，占用的空间会非常大，考虑一下有无其他简便的方法？

 

使用两个指针，分别以不同的速度向前遍历，一个以单个元素为步长，另一个以两个元素为步长，如果两个元素步长的指针追上了后面的指针，这便证明该链表中存在环。这样，只需要额外的两个空间，空间复杂度为O(1)。

 

/**
     * 使用两个指针，一个以速度1前进，另一个以速度2前进，如果存在闭环，则必定会出现交叉碰面
     * @param link
     * @param <T>
     * @return
     */
    public static <T> boolean containsCircle2(Link<T> link) {
        if (link == null || link.getNext() == null) {
            return false;
        }
        Link<T> first = link;
        Link<T> second = link.getNext();
        while (second != null && second.getNext() != null && second.getNext().getNext() != null) {
            first = first.getNext();
            second = second.getNext().getNext();
            if (first.getValue() == second.getValue()) {
                return true;
            }
        }
        return false;
    }