企业网站的作用/如何弄一个自己的网站

在前面的文章里已经讲解过如何判断一个单链表中是否存在环，那么今天就是进阶版的题目，题目链接如下：

虽说是进阶版，但是题目的解题思路基本上跟之前没有太大的区别，唯一不同的是这个题除了要判断有没有环之外，还要返回环最先开始的那个节点，所以参考上一题的思路，第一个最容易想到的方法就是借用一个set来记录已经遍历过的节点，如下：

class Solution(object):def detectCycle(self, head):s = set()while head:if head in s:  # 每当遍历一个新节点时，看看当前节点是否之前已经遍历过return headelse:s.add(head)head = head.nextreturn None

上面这个解题思路已经基本可以满足要求了，但是前面也提到需要用到额外O(n)的存储空间，所以在上一篇文章中提出了一快一慢两个指针，利用龟兔赛跑的方式来判断链表是否有环，但是这里还要找到并返回环开始的那个节点，So 我们在这里停一停，分析一下两个指针相遇时是什么状况：

此时fast指针比slow指针多走了一个环的距离，slow指针走的路径是3->2->0->-4，而fast指针走的路径是3->2->0->-4->1->0->-4，我们很容易知道fast走的路径长度是slow指针路径长度的2倍，那么3->2->0->-4->1->0->-4(注意我这里说的是走过的路径，并不是fast指针遍历的节点，实际fast指针遍历的节点是：3->0->1->-4)中前面加粗的路径是跟slow指针是一样的，又因为2倍长度的关系，那么意味着3->2->0->-4和-4->1->0->-4这两段路径的长度是一模一样的，而且0->-4这段路径是公共的，所以从3->2->0和-4->1->0的长度也是一样

当头指针从3遍历到0的时候，此时让fast指针挨个节点遍历，也会刚好在0这个节点和头指针相遇，至此我们就找到环开始的节点了。代码如下：

class Solution(object):def detectCycle(self, head):slow, fast, flag = head, head, Falsewhile fast and fast.next and fast.next.next:slow = slow.nextfast = fast.next.nextif slow is fast:   # 当两个指针相遇时，停止遍历flag = Truebreakif not flag: # 如果没有环return Noneelse:slow = head  while slow != fast:slow = slow.next  # 让slow指针从head开始挨个遍历fast = fast.next  # 让fast指针从相遇的那个节点开始挨个遍历return slow

分析一下下是不是很简单呢!