Leetcode打卡五：对于一个给定的链表，返回环的入口节点，如果没有环，返回null 拓展： 你能给出不利用额外空间的解法么？

题目：

对于一个给定的链表，返回环的入口节点，如果没有环，返回null
拓展：你能给出不利用额外空间的解法么？

题目理解：

1.这道题目的思路其实还是很清楚的，大致总共分为两步，第一步是判断是否有环，第二步是找到环的入口
2.判断有环还是使用快慢节点来判断，是否快节点和慢节点是否可以相遇
3.至于在相遇之后如何来找到环的入口节点，其实这个是一个数学的问题

如何找到入口节点：

这里我们先设几个值：
1.设从头结点到环的入口节点距离为n，入口节点到相遇节点的距离为m
2.那么慢节点走的路程为n+m，而快节点走的路程为慢节点的两倍2*(m+n）
3.然后其实快节点走的路程还有一种表达形式，我们设快节点第一次经过节点a（也是相遇节点）之后直到第二次和慢节点相遇在a点的这段路程为kL，k为这段时间快节点绕了几圈，L为环的长度。
4.根据3可得，直到相遇时刻，快节点实际的移动路程为m+n+kL，那么这个路程也等于2*(m+n），我们可得k*L=m+n
5.也就是说快节点两次经过a节点的路程就是m+n，那么我们就可以看到，从a节点出发，慢节点走n步就可以到入口节点，但是这个n我们是不知道的，所以我们让快节点重新指向头结点，之后一次走一步，慢节点从a节点出发，两者相遇的地方就是入口节点

public static ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return  null;
        ListNode slowNode = head;
        ListNode fastNode= head;
        Boolean hasRing = false;
        while(fastNode != null && fastNode.next != null && fastNode.next.next != null){//判断有无环
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if(slowNode == fastNode) {
                hasRing = true;
                break;
            }
        }
        if(hasRing == false)  return  null;

        ListNode crashNode = slowNode; //记录相遇节点
        fastNode = head;
        while(fastNode != null && fastNode.next != null){
            fastNode = fastNode.next;
            slowNode = slowNode.next;

            if(slowNode == fastNode) break;
        }

        return  slowNode;

    }