题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。 为了示意给定链表中的环，评测零碎外部应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。

输出：head = [3,2,0,-4], pos = 1输入：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连贯到第二个节点。输出：head = [1], pos = -1输入：返回 null解释：链表中没有环。

遍历+哈希

最简略的方法就是遍历每个节点，同时把节点存到一个字典中，当遍历下一个节点时，看看该节点是否曾经存在于字典中，如果是，就阐明该节点是环入口节点

def detectCycle(head: ListNode) -> ListNode:    hashTable = {}    while head:        if head in hashTable:            return head        hashTable[head] = 1        head = head.next    return None

工夫复杂度：O(n)
空间复杂度：O(n)

双指针

了解双指针的思路，须要通过画图，计算挪动间隔的等量关系来了解：

在链表头节点，定义两个指针：fast和slow
fast每次挪动2个节点，slow每次挪动1个节点

如果链表没有环，fast指针会先挪动到null处
如果链表有环，fast先进入环，slow随后进入环，最终他们必定会在环中的某个节点相遇

假如fast和slow第一次相遇时的节点如图所示
a代表链表头节点到环的入口节点的节点数
b代表环的入口节点到fast和slow第一次相遇的节点的节点数
c代表第一次相遇节点到环的入口节点的节点数

此时，fast走过的节点数为 a+b+n(c+b) ，n示意fast在环中绕的圈数
slow走过的节点数为 a+b
fast和slow是一起挪动的，所以任意时刻他们的挪动步数是雷同的，然而fast每次挪动2个节点，雷同的步数下，fast挪动的节点数应该是slow的2倍
所以 a+b+n(c+b) = 2(a+b)
整顿等式得：a=n(b+c)-b = nb+nc-b = (n-1)b+nc = (n-1)b+(n-1)c+c=(n-1)(b+c)+c
得 a = (n-1)(b+c)+c
也就是说：头节点到环入口节点的间隔 = 第一次相遇节点到环入口节点的间隔+(n-1)圈环的长度
如果此时有两个指针a和b，a从头节点开始挪动，b从slow和fast第一次相遇节点开始挪动，均每次挪动一个节点，a和b最终会在环入口节点处相遇。
此时，slow曾经处在第一次相遇节点地位，因而当slow和fast第一次相遇时，再在头节点处定义一个指针，和slow一起每次挪动1个节点，他们相遇的那个节点就是环入口节点。

def detectCycle(self, head: ListNode) -> ListNode:    # 排除空链表状况    if not head:        return None    fast,slow,ptr = head,head,head    while fast:        # 排除链表只有一个节点的状况        if not fast.next:            return None        # 挪动fast和slow        slow = slow.next        fast = fast.next.next        # fast和slow相遇时        if slow == fast:            # ptr和slow开始挪动，直到相遇            while ptr != slow:                slow = slow.next                ptr = ptr.next            # 相遇时，返回该节点，就是入口节点            return ptr           return None# 跟简洁优雅版def detectCycle(self, head: ListNode) -> ListNode:    fast, slow = head, head    while True:        if not (fast and fast.next): return        fast, slow = fast.next.next, slow.next        if fast == slow: break    fast = head    while fast != slow:        fast, slow = fast.next, slow.next    return fast

工夫复杂度：O(N)，其中 N 为链表中节点的数目。在最后判断快慢指针是否相遇时，slow 指针走过的间隔不会超过链表的总长度；随后寻找入环点时，走过的间隔也不会超过链表的总长度。因而，总的执行工夫为 O(N)+O(N)=O(N)。

空间复杂度：O(1)。咱们只应用了slow,fast,ptr 三个指针。