寻找环状链表的入口_链表有环怎样找入口

这里的问题是如果知道了一定有入口，那么如何确定入口的位置呢？方法非常简单，但是要理解清楚有些难度。
先说结论先按照快慢方式寻找到相遇的位置（假如为下图中Z），然后将两指针分别放在链表头（X）和相遇位置（Z），并改为相同速度推进，则两指针在环开始位置相遇（Y）。
结论很简单，但这是为什么呢？
①先看假如一圈就遇到的情况

为了便于理解，我们首先假定快指针在第二次进入环的时候就相遇了：
此时的过程是：
1.找环中相汇点。分别用fast、slow表示快慢指针，slow每次走一步，fast就走两步，直到在环中的某个位置相会，假如是图中的Z。
2.第一次相遇：
那么我们可以知道fast指针走了a+b+c+b步，
slow指针走了a+b步
那么：
2*(a+b) = a+b+c+b
所以a = c
因此此时让slow从Z继续向前走，temp从起点开始走，两个同时开始走（两个每次都走一步），一次走一步那么它们最终会相遇在y点，正是环的起始点。

 public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null){
            slow=slow.next;
            if(fast.next!=null){
                fast=fast.next.next;
            }else {
                return null;
            }
            if(fast==slow){
                ListNode temp = head;
                while (temp!=slow){
                    temp=temp.next;
                    slow=slow.next;
                }
                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