JAVA 判断双向链表是否有环 原创

复制收展Javapackage com.algorithm.list;

/**
 * @Desc 累行客
 * 双向链表结构
 * @Author luolei
 * @Web http://www.leixingke.com/
 * @Date 2020/11/07 16:25
 */
public class DListNode<T> {

    T item;
    DListNode pre;
    DListNode next;

    DListNode(T item) {
        this.item = item;
        this.pre = null;
        this.next = null;
    }

    /*链表尾部添加结点*/
    public void add(T item) {
        if(this.next == null) /*如果当前结点的next为空，直接指向新结点*/
        {
            DListNode node = new DListNode(item);
            this.next = node;
            node.pre = this;
        }
        else /*如果当前结点的next不为空，向后扫描，直到遇到next为null的结点，将新结点插入*/
            this.next.add(item);
    }


    /*next打印链表*/
    public void print() {
        System.out.print(this.item);
        if(this.next != null) {
            System.out.print("--->");
            this.next.print();
        }else{
            System.out.println();
        }
    }
    /*pre打印链表*/
    public void print2() {
        System.out.print(this.item);
        if(this.pre != null) {
            System.out.print("--->");
            this.pre.print2();
        }else{
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

判断双向链表是否有环

复制收展Javapackage com.algorithm.list;

/**
 * @Desc 累行客
 * 判断双向链表是否有环
 * @Author luolei
 * @Web http://www.leixingke.com/
 * @Date 2020/11/07 14:34
 */
public class hasCycleDListSolution {

    /**
     * @Desc:  判断双向链表是否有环 快慢指针遍历法
     *
     *  思路：定义两个指针 fast 和 slow，两者初始指向链表头，slow每次前进一步，fast每次前进两步。
     *  快指针能不能继续往下走 fast != null && fast.next != null
     *  如果有环，那么快指针一定能追上慢指针，若 slow 和 slow 在某时刻指向同一结点，则说明该链表有环。
     *
     *  快慢指针，当快慢指针相遇时，快指针比慢指针多走了环长度的整数倍，而且快指针比慢指针多走的多走的和慢指针走的一样，
     *  所以慢指针走的步数也是环长度的整数倍！此时让快指针再从头走，速度和慢指针一样，两指针肯定会在环入口相遇。
     *
     * 双向链表需要两步
     *  1、从第一个结点开始，判断next指针是否可能出现环
     *  2、从第一个结点开始，判断next指针没有出现环，接着从最后一个结点开始，判断pre指针是否可能出现环，从最后一个结点，向前扫描
     * @param head: 第一个结点
     * @return: boolean
    */
    public static boolean hasCycle(DListNode head) {
        /*1、从第一个结点开始，判断next指针是否可能出现环*/
        /*第一个结点为空 或 只有一个结点*/
        if(head == null || head.next == null) return false;
        DListNode slow=head;
        DListNode fast=head;
        while(fast != null && fast.next != null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow == fast) return true;
        }

        /*2、从第一个结点开始，判断next指针没有出现环，接着从最后一个结点开始，判断pre指针是否可能出现环，从最后一个结点，向前扫描*/
        DListNode next = head.next;
        while (next.next != null){
            next = next.next; /*得到尾结点*/
        }

        DListNode slow2=next;
        DListNode fast2=next;
        while(fast2 != null && fast2.pre != null){
            slow2=slow2.pre;
            fast2=fast2.pre.pre;
            if(slow2 == fast2) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        /*创建链表，第一个结点*/
        DListNode ln = new DListNode(1);
        ln.add(2);
        ln.add(3);
        ln.add(4);
        ln.add(5);
        ln.add(6);

        /*创造环1
        * 1--->2--->3--->4--->5--->
        * 3--->4--->5--->
        * ...
        * 3--->4--->5
        * */
        DListNode node = ln.next.next.next.next;
        node.next=ln.next.next;
        /*next输出*/
        /*ln.print();*/

        /*创造环2
        * 6--->5--->4--->3--->2--->
        * 6--->5--->4--->3--->2
        * ...
        * 6--->5--->4--->3--->2
        * */
        /*DListNode node2 = ln.next;
        node2.pre=ln.next.next.next.next.next;

        DListNode next = ln.next;
        while (next.next != null){
            next = next.next; *//*得到尾结点*//*
        }
        *//*pre输出*//*
        next.print2();*/

        System.out.println(hasCycle(ln));
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95