---

NC03

描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围：

要求：空间复杂度 ，时间复杂度

示例1

输入：

{1,2},{3,4,5}

返回值：

3

说明：

返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3      

思路

使用NC03快慢指针

当链表无环时返回null

若链表有环 ，两指针在环内第一次相遇时，此时将slow指针指向头结点，然后fast和slow都走一步，直到再次相遇 此时的节点节点就是入环节点。

推导

如上图，是一个环形链表，设环外长度为a，指针slow进入环内后又走了长度b在q点和fast指针相遇

在相遇之前fast指针可能已经在环内走了n圈 故此时fast走过的距离为 a+n(b + c) + b

slow指针走过的距离为 a + b

又因为fast指针走过的距离为slow的二倍 故有 2(a + b ) = a + n(b + c) + b

化简上式得 a = (n - 1)(b + c ) + c

因为b + c 等于环长

所以上式的含义为链表头到入环节点p的距离等于从相遇点到入环节点的距离c 加上n-1被的环长

所以用c， h两个指针从p点和head开始走，当h走完A时，c走过的路为C + (n-1)(C+B)，即n圈+C，所以h和c的相遇点为q

代码

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null && pHead.next == null) {
            return null;
        }
        // 判断是否有环

        ListNode slow = pHead;
        ListNode fast = pHead;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 相遇
            if (slow == fast) {
                slow = pHead;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;

    }
}

Q.E.D.