Leetcode系列之链表（2）

题目2：

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

  拓展：

  你能给出不利用额外空间的解法么？

思路：

1.判断链表是否有环：如果有环，快慢指针一定会相遇，而且相遇点必然在环内（快慢指针）

2.查找环的入口：（数学模型推理）

由1所知，设计数学模型1如下图（O为快慢指针的起点，E为环的入口点，M表示快慢指针的相遇点）（模型2所有的点都是入口，不需要讨论）

链表的总长度为：OE+n（OE表示线段长度，n表示圆环的长度），当OE+EM步的慢指针与快指针相遇与M点，快指针已在环内走了k圈

由于快指针永远是慢指针步长的两倍，于是在第一次相遇点有，2(OE+EM)=OE+k*n+EM，求OE得，OE=k*n-EM

也就是说，慢指针从O点出发到E点，快指针从M点顺时针出发走k圈，会相遇于E点（E点就是我们要找的入口）

ps：同向出发切的思维切换到，以慢指针从起点出发，快指针从相遇点开始出发的思维（是不是觉得很熟悉，没错与小学考试的路程相遇点题目很类似！！！）

代码：

/**

* Definition for singly-linked list.

* class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) {

*        val = x;

*        next = null;

*    }

* }

*/

public class Solution {

    public ListNode detectCycle(ListNode head) {

        if(head==null||head.next==null){

            return null;

        }

        ListNode fast=head;

        ListNode slow=head;

        while(fast.next!=null&&fast.next.next!=null){

            fast=fast.next.next;

            slow=slow.next;

            if(fast==slow)break;

        }

        if(fast.next==null||fast.next.next==null){

            return null;

        }

        slow=head;

        while(slow!=fast){

            slow=slow.next;

            fast=fast.next;

        }

        return slow;

    }

}