142. Linked List Cycle II

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

When checking whether there is cycle in the linked list, we have to verify that fast.next.next is always safe to access.

And after we find the first meet point, the cycle is promised. So that we can just walk the pointers blindly until their next meet.

Prof of the second stage: let's assum there are A steps before entry point and B steps from entry point to the first meeting point. It means that, fast node moves 2 (A + B) steps totally. And, within the cycle, fast nodes will move A + B steps to arrive again at the first meet point, which also means A steps to arrive the entry point since there are B steps between entry point and first meet point.