Linked List Cycle II

Question Description

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?

Solution

For detecting the cycle in linked list, we can use the fast and slow pointers.

However, if we wanna know the beginning of cycle, we need to do some math work.

From the fast and slow pointers we know:

$$fast = 2 * slow$$

If the cycle exists, and we are at the kth element in the cycle, assume we have x elements outside cycle and y elements in the cycle.

$$fast = x + k + n y, slow = x + k + m y$$

And we can get x + k = (m - n) * y.

So if we want to reach the beginning of cycle, we only need to go x steps further from the kth position.

One thing subtle here is that if you make the count from None, you must let the beginning of second traversal also be None, not head.

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        one, two = head, head.next
        while one != two:
            if one:
                one = one.next
            if two:
                two = two.next
            if two:
                two = two.next
        if not one:
            return None
        one = None
        while two != one:
            two = two.next
            if not one:
                one = head
            else:
                one = one.next
        return two

In this code, if you make the one equals to head at the second traversal, you will get TLE because the one and two pointers will never meet(they have one node distance).