Linked List Cycle II

'''
First part
Let the length of linear part of linked list be x and the circular part be y. So, when the slow pointer reaches tge start of cycle(i.e covered x+1 nodes), the fast pointer would be (x+1)%y distance ahead. This is becoz normally the fast pointer would have been x+1 nodes ahead but since fast pointer has already entered the cycle, the distance b/w them would be (x+1)%y.Thus, we can say that the slow pointer is y-x%y-1 ahead of fast pointer(clockwise). Since the relative speed of both pointer is 1x(2x of fp-1x of sp), this gap would reduce to zero in y-x%y-1 iterations and by this time slow pointer would have travelled y-x%y-1 nodes from cycle start. Thus fp==sp at y-x%y-1 nodes from cycle start(clockwise from cycle start) or we can say x%y+1 nodes from cycle start(Anticlockwise from cycle start)
Sexond part
Now we take two pointers p1, p2 one starting from head and other starting from sp.next(one node clockwise ahead of the meeting point of fp and sp).
Thus when p1 advances x times, we can say that it travels q no. of y nodes and x%y nodes (q=floor(x/y)). Since p2 moves at same speed as p1 it also travels q no. of y nodes and x%y nodes. But since travelling any number of y nodes in the cycle brings us to our starting point(in this case one node ahead of where fp and sp had met), total effective nodes travelled is x%y from strating point of p2(clockwise), which is nothing but the starting point of cycle(as already shown in first part that starting point is x%y+1 nodes ahead of meeting point of fp and sp). Also p1 has reached the starting point of cycle (as by this time it has travelled x nodes). Thus meeting point of p1 and p2 is starting point of cycle.
'''
class Solution(object):
    def detectCycle(self, head):
        if not head:
            return head
        sp, fp = head, head.next
        while fp is not None and fp.next is not None and sp != fp:
            sp = sp.next
            fp = fp.next.next
        if sp == fp:
            p1 = head
            p2 = sp.next
            while p1 != p2:
                p1 = p1.next
                p2 = p2.next
            return p1
        else:
            return None