Leetcode 141 与 Leetcode 142 题类似，Leetcode 141 为判断链表是否有环，而Leetcode 142在判断若有环基础上返回起始环的节点。
- Leetcode 141：
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析： 设置一个快指针fast、一个慢指针slow。由于我们知道若有环，快慢指针将一直"跑"下，没有终点，并且快慢指针一定会相遇；如同在没有设置终点暂停的情况下，两人从同一起点出发以不同速度在环形跑道上跑步，跑得快的同学最终会出现比跑得慢的同学多跑一圈并且相遇的情形。 这里设置为快指针跑两步时，慢指针跑一步，两者速度比为2:1。
Python代码：
class Solution(object):
def hasCycle(self, head):
fast = slow = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
- Leetcode 142：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
分析：此题在 Leetcode 141的基础上，添加了若有环即返回其环起始位置的步骤。同 Leetcode 141分析中所述，若设定快指针每跑两步，慢指针跑一步，两者速度比为2:1，即在相同时间内，两者跑得距离之比也为2:1。如图，当有环时，设置b点为环的起始位置，m点为快慢指针第一次相遇的位置，hb距离为x1，b到m距离为x2，m到b的距离为x3。由于同一起点出发，在相同时间内两者跑的距离之比为2:1，所以当他们在m点相遇时有 x1+x2+x3+x2 = 2(x1+x2)，即x1 = x3。
image
当快慢指针在m点相遇后，慢指针从m点出发，head指针从h点同时出发并以相同的速度前行，由于x1=x3，因此两者会在b点，即环的起始位置相遇。
Python代码：
class Solution(object):
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
while slow != head:
slow = slow.next
head = head.next
return head
return None
