LeetCode 142. Linked List Cycle II 20170706

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.

题目大意：给定一个链表，如果该链表存在环，返回环的起点。如果不存在，返回null

解题思路：本题是一道有趣的行程问题。在这里给出该行程问题的推导。

假设有两个快慢指针fast和slow，其中fast一次走两步，slow一次走一步，两者同时出发，由于存在环，所以必定会在某点相遇。设head到环起点距离为a，起点距离到相遇点距离为b，环长度为c。则fasts=2slows，slows=a+b，fasts=a+b+n*c，所以可知slows=n*c，a=n*c-b。当相遇后，令slow返回head，两者同时以每次一步的速度前进。slow从head走到起点走了a，fast也相遇点走了a，因为a=n*c-b=(n-1)*c+c-b，所以可知a+b=n*c，fast恰好也走回了起点。这样就能把每个变量都求出来，就能求出起点位置了。

class Solution(object):
　　def detectCycle(self, head):
　　　　"""
　　　　:type head: ListNode
　　　　:rtype: ListNode
　　　　"""
　　　　if head == None or head.next == None:
　　　　　　return None
　　　　slow = fast = head
　　　　while fast and fast.next:
　　　　　　slow = slow.next
　　　　　　fast = fast.next.next
　　　　　　if fast == slow:
　　　　　　　　break
　　　　if slow == fast:
　　　　　　slow = head
　　　　　　while slow != fast:
　　　　　　　　slow = slow.next
　　　　　　　　fast = fast.next
　　　　　　return slow
　　　　return None