Python 环形 链表 Linked List Cycle II No.142

其实和第141的思路大概一样，也是分为两种，不过第二种涉及到一些数学证明，有一点tricky。这题我还有一个不明白的就是，我第一次看到这题目的时候，为什么返回值是node，而不是index，我已知理解是输出一段文字，包含它的index。（我是菜鸡，谁能留言说一下，万分感谢）

#第一种方法，在141的基础上改进了一下，这样写更简单，直观
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""visited = set()p = headwhile p is not None:if p in visited:return pelse:visited.add(p)p = p.nextreturn None

第二种方法快慢指针法，首先我来个数学证明（顺便吐槽一下官方评论下面的莫名的图解算法，都说的什么东西，说的都不对，醉了，害人害己，不过还是要借用别人的图用一下）

AB是没有环的区域，假设D是相遇的地方。那么就有了如下的公式：
慢指针走过的距离是AB + BD，
那么快指针走过的距离AB + n(BCDEB) +BD(就是如果AB距离很长的话，环又很小的话，就会导致快指针一直在转圈圈，爱的魔力转圈圈，设置为n圈)
由于慢指针走一格，快走两格，那么他们距离公式就有2倍的关系。
so：

AB + n(BD+DEB) +BD = 2 *（AB + BD）
化简之后就得到了，AB= n-1（(BD+DEB）+ DEB
你可能会觉得，这个有啥子用？然并卵? 对不起，确实有用。
当快指针和慢指针在D点相遇了，那么我们只需要把快指针，拿到A点，并且把它的移动速度改为和慢指针一样，一次移动一格。这样的话，他们一定会在B点相遇（因为距离一样），这个B也就是我们需要找到的node。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""fast = slow = headwhile True:if not (fast and fast.next):return fast, slow= fast.next.next, slow.nextif fast is slow:breakfast = headwhile not (fast is slow):fast,slow = fast.next, slow.nextreturn fast