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
