JAVA 判断单链表是否有环 和 返回环的入口 原创

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。

思路：定义两个指针 fast 和 slow，两者初始指向链表头，slow每次前进一步，fast每次前进两步。
快指针能不能继续往下走 fast != null && fast.next != null
如果有环，那么快指针一定能追上慢指针，若 slow 和 slow 在某时刻指向同一结点，则说明该链表有环。

快慢指针，当快慢指针相遇时，快指针比慢指针多走了环长度的整数倍，而且快指针比慢指针多走的多走的和慢指针走的一样，
所以慢指针走的步数也是环长度的整数倍！此时让快指针再从头走，速度和慢指针一样，两指针肯定会在环入口相遇。

单链表结构  

复制收展Javapackage com.algorithm.list;

/**
 * @Desc 累行客
 * 单链表结构
 * @Author luolei
 * @Web http://www.leixingke.com/
 * @Date 2020/11/07 15:06
 */
public class ListNode<T>{
    T item;
    ListNode next;
    /*构造函数*/
    ListNode(T item){
        this.item=item;
        this.next=null;
    }
    /*添加新的结点*/
    public void add(T item) {
        if(this.next == null) /*如果当前结点的next为空，直接指向新结点*/
            this.next = new ListNode(item);
        else /*如果当前结点的next不为空，向后扫描，直到遇到next为null的结点，将新结点插入*/
            this.next.add(item);
    }
    /*打印链表*/
    public void print() {
        System.out.print(this.item);
        if(this.next != null) {
            System.out.print("--->");
            this.next.print();
        }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

1、判断单链表是否有环

2、返回环的入口  

复制收展Javapackage com.algorithm.list;

/**
 * @Desc 累行客
 * 判断单链表是否有环
 * 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。
 * 有环链表的定义：在链表中某个节点的next元素指向在它前面出现过的节点，则表明该链表存在环路。
 * @Author luolei
 * @Web http://www.leixingke.com/
 * @Date 2020/11/07 14:34
 */
public class hasCycleSolution {

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

    /**
     * @Desc: 返回环的入口
     * 快慢指针，当快慢指针相遇时，快指针比慢指针多走了环长度的整数倍，而且快指针比慢指针多走的多走的和慢指针走的一样，
     * 所以慢指针走的步数也是环长度的整数倍！此时让快指针再从头走，速度和慢指针一样，两指针肯定会在环入口相遇。
     *  slow 和 fast
     * 第一次相遇说明有环
     * 第二次相遇即是环入口
     * @param head:
     * @return: com.algorithm.list.ListNode
    */
    public static ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow=head;
        ListNode fast=head;
        while (fast != null && fast.next != null) {
            slow=slow.next;
            fast=fast.next.next;
            /*第一次相遇说明有环*/
            if (slow == fast) {
                fast = head;
                /*第二次相遇即是环入口*/
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }


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

        /*创造环*/
        ListNode node = ln.next.next.next.next.next;
        node.next=ln.next.next;

        /*判断是否有环*/
        System.out.println(hasCycle(ln));
        /*环入口*/
        System.out.println(detectCycle(ln).item);

        /*输出*/
        ln.print();

    }

}
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
96
97
98

扩展

JAVA 判断双向链表是否有环