Python LeetCode-142. 环形链表 II（pyt

LeetCode原链接

1.题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

示例1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：

你是否可以不用额外空间解决此题？

2.分析

图和正统的思路引用自风澈云间/ 南郭子綦

• 第一步当然是判断是否有环：思路LeetCode-141. 环形链表（难度-简单）
• 从链表头到环路起点步数为K，从起点到相遇点步数为M，环路长度为L。
  那么我们有，快慢指针相遇时所走过的步数：
  step_slow = K + M
step_fast = K + M + n*L
  又因为快指针每次都多走一步：
  step_faster = 2 * step_slow
  由以上三个公式可以推断出
  K ＝ (n-1)L + L - M
  所以，当快慢指针在相遇点相遇后，让slow指针回到head，fast留在相遇点。然后同时向前走，两个指针都是每次走一步，这样当慢指针走到起点时，快指针也会走到起点。

• 示意图：

  
  

部分思路来自这个博客
上面的思路过于粗暴，这个更具数学归纳性

3.解决

代码是自己撸的

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                slow= head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None