如果有一串单链表，这个链表可能是循环链表，也可能不是，那该如何判断呢？

可以设置两个变量p和q，每次p走一步，q从0开始走到p，判断它们的步数是否相等，如果没有回路，那么它们步数是相等的，如果步数不相等，那就意味着出现了回路。 下面是步骤图示

下一步就尤为关键了

P是每次只走一步，从上一个节点开始走。而q每次从最前面的节点开始走，当p从最后一个节点走向下一个节点，而q从0开始走到q，自然步数就不一样了。

代码实现:

public class CycleCheck {
    private class Data{
        int num;
        Data next = null;
        public Data(int num){
            this.num = num;
        }
    }

    Data head = new Data(0);
    public void insertE(int num){
        Data cur = head;
        while(true){
            if(cur.next == null){
                cur.next = new Data(num);
                break;
            }
            cur = cur.next;
        }
    }

    public void display(){
        Data cur = head.next;
        int 最大输出 = 20;
        while(cur!=null){
            System.out.print(cur.num+"   ");
            cur = cur.next;

            if(最大输出-- < 0) break;
        }
        System.out.println("\n");
    }
}

单链表类，节点类，尾插法插入数据，显示数据。 因为会出现循环链表，因此设定一个最大输出，不然会死循环。

//  手工造一个带环的链表
public void 把最后一个节点指向(int 某个节点){
    // 这个方法名是不是很直白 ...
    if(head.next == null) return;
    int length = 0;
    Data cur = head.next;
    Data tail = cur;
    while(cur!=null){
        length++;
        tail = cur;
        cur = cur.next;
    }
    if(length < 3){
        System.out.println("链表小于三个节点，无法成环");
    } else if(某个节点 >= length-2 || 某个节点 < 0){
        System.out.println("无法指向该节点");
    } else {
        cur = head.next;
        for(int i = 0; i < 某个节点; i++){
            cur = cur.next;
        }
        tail.next = cur;
    }
}

额，因为想不到变量名，就用中文好了，嘻嘻

上面几张示意图的代码实现

//  成环检查
public void check(){
    Data p = head.next;
    int pStep = 0;
    while(p!=null){
        p = p.next;
        pStep++;

        Data q = head.next;
        int qStep = 0;
        while(q != p){
            q = q.next;
            qStep++;
        }

        if(pStep != qStep){
            System.out.println("链表在 第"+qStep+"节点 处成环");
            return;
        }
    }
     System.out.println("链表不存在环");
}

测试测试~

public static void main(String[] args){
    CycleCheck cc = new CycleCheck();

    System.out.println("\n\n插入数据 0 1 2 3 4 5 6");
    cc.insertE(0);
    cc.insertE(1);
    cc.insertE(2);
    cc.insertE(3);
    cc.insertE(4);
    cc.insertE(5);
    cc.insertE(6);
    cc.display();

    System.out.println("是否存在环？");
    cc.check();

    System.out.println("\n将最后一个节点指向第3个节点");
    cc.把最后一个节点指向(3);
    cc.display();
    System.out.println("可以看到链表输出了一段循环 3456，如果没有限制最大输出会无限输出（即死循环）\n\n");

    System.out.println("是否存在环?");
    cc.check();

}

输出内容

插入数据 0 1 2 3 4 5 6
0   1   2   3   4   5   6   

是否存在环？
链表不存在环

将最后一个节点指向第3个节点
0   1   2   3   4   5   6   3   4   5   6   3   4   5   6   3   4   5   6   3   4   5   

可以看到链表输出了一段循环 3456，如果没有限制最大输出会无限输出（即死循环）


是否存在环?
链表在 第3节点 处成环

完整代码

public class CycleCheck {
    private class Data{
        int num;
        Data next = null;
        public Data(int num){
            this.num = num;
        }
    }

    Data head = new Data(0);
    public void insertE(int num){
        Data cur = head;
        while(true){
            if(cur.next == null){
                cur.next = new Data(num);
                break;
            }
            cur = cur.next;
        }
    }

    public void display(){
        Data cur = head.next;
        int 最大输出 = 20;
        while(cur!=null){
            System.out.print(cur.num+"   ");
            cur = cur.next;

            if(最大输出-- < 0) break;
        }
        System.out.println("\n");
    }

    //  手工造一个带环的链表
    public void 把最后一个节点指向(int 某个节点){
        // 这个方法名是不是很直白 ...
        if(head.next == null) return;
        int length = 0;
        Data cur = head.next;
        Data tail = cur;
        while(cur!=null){
            length++;
            tail = cur;
            cur = cur.next;
        }
        if(length < 3){
            System.out.println("链表小于三个节点，无法成环");
        } else if(某个节点 >= length-2 || 某个节点 < 0){
            System.out.println("无法指向该节点");
        } else {
            cur = head.next;
            for(int i = 0; i < 某个节点; i++){
                cur = cur.next;
            }
            tail.next = cur;
        }
    }

    //  成环检查
    public void check(){
        Data p = head.next;
        int pStep = 0;
        while(p!=null){
            p = p.next;
            pStep++;

            Data q = head.next;
            int qStep = 0;
            while(q != p){
                q = q.next;
                qStep++;
            }

            if(pStep != qStep){
                System.out.println("链表在 第"+qStep+"节点 处成环");
                return;
            }
        }
         System.out.println("链表不存在环");
    }



    public static void main(String[] args){
        CycleCheck cc = new CycleCheck();

        System.out.println("\n\n插入数据 0 1 2 3 4 5 6");
        cc.insertE(0);
        cc.insertE(1);
        cc.insertE(2);
        cc.insertE(3);
        cc.insertE(4);
        cc.insertE(5);
        cc.insertE(6);
        cc.display();

        System.out.println("是否存在环？");
        cc.check();

        System.out.println("\n将最后一个节点指向第3个节点");
        cc.把最后一个节点指向(3);
        cc.display();
        System.out.println("可以看到链表输出了一段循环 3456，如果没有限制最大输出会无限输出（即死循环）\n\n");

        System.out.println("是否存在环?");
        cc.check();

    }
}