数据结构使用快慢指针找出有环链表入口_快慢指针循环链表入口

当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。证明这一结论牵涉到数论的知识，这里略，只讲实现。


这是一个哔哩哔哩老师错误的代码（bilibili里的2020JAVA基础-深入系统的学习数据结构与算法），我觉的逻辑是有一定的问题，会出现死循环。
什么情况呢？？？？？
当有环链表出现足够长的没环的地方，此时就有可能出现死循环，当圆环节点数为3时，slow和fast相遇只需要3步，当前边足够长temp还没走到，他们又相遇了，temp又指向了first,所以这个逻辑肯定会出现死循环。错误代码如下。。。。。。
使用我的下边图像，使用上边的错误代码，老师的逻辑一定是错的（自己去画）

我画了一下正确代码的图像（根据我的代码逻辑）。

public class QuickSlowMid {
    //节点类
    private static class Node<T> {
        T item;
        Node next;
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Node<String> one = new Node<>("a", null);
        Node<String> two = new Node<>("b", null);
        Node<String> three = new Node<>("c", null);
        Node<String> four = new Node<>("d", null);
        Node<String> five = new Node<>("e", null);
        Node<String> six = new Node<>("f", null);
        Node<String> seven = new Node<>("g", null);
        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        five.next = six;
        six.next = seven;
        seven.next = five;
        Node entrance = getEntrance(one);
        System.out.println(entrance.item);
    }

    public static Node getEntrance(Node node) {
        Node fast = node;
        Node slow = node;
        Node temp = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                temp = node;
                continue;
            }

            if (temp != null) {
                temp = temp.next;
                if (temp == slow) {
                    break;
                }

            }
        }

        return temp;
    }

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

正确的代码：
不满足这种状况（一个圆环）
满足所有有环情况。

public class QuickSlowMid {
    //节点类
    private static class Node<T> {
        T item;
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Node<String> one = new Node<>("a", null);
        Node<String> two = new Node<>("b", null);
        Node<String> three = new Node<>("c", null);
        Node<String> four = new Node<>("d", null);
        Node<String> five = new Node<>("e", null);
        Node<String> six = new Node<>("f", null);
        Node<String> seven = new Node<>("g", null);
        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        five.next = six;
        six.next = seven;
        seven.next = seven;
        Node entrance = getEntrance(one);
        System.out.println(entrance.item);
    }

    public static Node getEntrance(Node node) {
        Node fast = node;
        Node slow = node;
        Node temp = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                temp = node;
                while (true){
                    temp=temp.next;
                    slow=slow.next;
                    if (slow==temp){
                        return temp;
                    }
                }
            }
        }
        return null;
    }


}

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