更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

链表中环的入口结点

问题描述

LeetCode 剑指 Offer II 022. 链表中环的入口节点

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

分析问题

拿到这个问题，我们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否已经被访问过。如果被访问过，就代表这个结点是链表中环的入口点，我们直接返回就好。如果没有被访问过，我们就标记一下，然后接着去遍历下一个结点，直到遍历完整个链表为止。下面我们来看一下代码的实现。

def EntryNodeOfLoop(self, pHead):
        tags = set()
        while pHead:
            #表示已经被访问过了，代表有环
            if pHead in tags:
                return pHead
            tags.add(pHead)
            pHead = pHead.next
        return None

我们可以看到该算法的时间复杂度和空间复杂度都是O(n)。

优化

我们这里也可以采用快慢指针来求解，就和上一题的解法类似，我们来看一下。

我们可以使用两个指针fast和slow。他们都从链表的头部开始出发，slow每次都走一步，即slow=slow->next，而fast每次走两步，即fast=fast->next->next。如果链表中有环，则fast和slow最终会在环中相遇。

我们假设链表中环外的长度为a，show指针进入环后又走了b的距离与fast相遇，此时fast指针已经绕着环走了n圈。所以快指针一共走了a+n(b+c)+b=a+(n+1)b+nc的距离，我们知道快指针每次走2步，而慢指针每次走一步，所以，我们可以得出快指针走的距离是慢指针的两倍，即a+(n+1)b+nc=2(a+b)，所以a=c+(n-1)(b+c)。这里你会发现：从相遇点到入环的距离c，再加上n-1圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现slow和fast相遇时，我们再额外使用一个指针ptr指向链表头部，然后它和slow指针每次都向后移动一个位置。最终，他们会在入环点相遇。

Tips: 你也许会有疑问，为什么慢指针在第一圈没走完就会和快指针相遇呢？我们来看一下，首先，快指针会率先进入环内。然后，当慢指针到达环的入口时，快指针在环中的某个位置，我们假设此时快指针和慢指针的距离为x，若x=0，则表示在慢指针刚入环时就相遇了。我们假设环的长度为n，如果看成快指针去追赶慢指针，那么快指针需要追赶的距离为n-x。因为快指针每次都比慢指针多走一步，所以一共需要n-x次就能追上慢指针，在快指针遇上慢指针时，慢指针一共走了n-x步，其中x>=0，所以慢指针走的路程小于等于n，即走不完一圈就会相遇。

下面，我们来看一下代码实现。

def detectCycle(head):
    if not head:
        return None
    #快慢指针
    slow = head
    fast = head
    while True:
        if not fast or not fast.next:
            return None
        fast=fast.next.next
        slow=slow.next
        #相遇时，跳出循环
        if fast == slow:
            break

    ptr = head
    while ptr != slow:
        ptr=ptr.next
        slow=slow.next
    return ptr

该算法的时间复杂度是O(n)，空间复杂度是O(1)。