寻找链表环的入口_找到环的入口

（寻找链表环的入口）
题解：

这个连同I都是很经典的题啦，刷CC150时候就折磨了半天。

其实就推几个递推公式就好。。首先看图（图引用自CC150）：

从链表起始处到环入口长度为：a，从环入口到Faster和Slower相遇点长度为：x，整个环长为：c。

明确了以上信息，就可以开始做运算了。。

假设从开始到相遇，Slower走过的路程长为s，由于Faster的步速是Slower的2倍，那么Faster在这段时间走的路程长为2s。

而对于Faster来说，他走的路程还等于之前绕整个环跑的n圈的路程nc，加上最后这一次遇见Slower的路程s。

所以我们有：

               2s = nc + s 
1

对于Slower来说，他走的路程长度s还等于他从链表起始处到相遇点的距离，所以有：

                s = a + x 
1

通过以上两个式子代入化简有：

                a + x = nc

                a = nc - x

                a = (n-1)c + c-x

                a = kc + (c-x)
1
2
3
4
5
6
7

那么可以看出，c-x，就是从相遇点继续走回到环入口的距离。上面整个式子可以看出，如果此时有个pointer1从起始点出发并且同时还有个pointer2从相遇点出发继续往前走（都只迈一步），那么绕过k圈以后， pointer2会和pointer1在环入口相遇。这样，换入口就找到了。

 //找到链表中环的入口点
    public static Node findLoopPort(Node head){
        //首先判断头结点是否为null
        if(head==null||head.next==null)
            return null;
        Node fast = head,slow=head;
        //找到相遇点fast
        while (true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            //找到
            slow = slow.next;
            fast = fast.next.next;

            if(fast == slow)
                break;
        }
        //相遇点与链表头分别设定一个指针,每次各走一步,相遇第一个点即为环入口点
        slow = head;//slow back to start point
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow; //when slow == fast, it is where cycle begins
    }
    @Test
    public void testIsLoop() {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n2;  //构造一个带环的链表,去除此句表示不带环
        boolean b = LinkedList.IsLoop(n1);
        System.out.println(b);//true

        Node loopPort = LinkedList.findLoopPort(n1);
        System.out.println(loopPort.data);
    }
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