共计 1508 个字符，预计需要花费 4 分钟才能阅读完成。
更多算法题解，关注公众号《程序员学长》
链表中环的入口结点
问题形容
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)。
更多算法题解，关注公众号《程序员学长》
