142. Linked List Cycle 2

Problem Statement in English

You’re given a linked list node head. Your task is to return the node at which the cycle begins, if there is a cycle in the linked list, and None otherwise.

Approach

I feel that to be able to solve this problem you need to know a little trick beforehand. We’ll get to that.

But first, this problem builds on a previous problem, where we used the Fast and Slow Pointer Technique to find the middle of a linked list.

But how do we find the node at which the cycle begins?

That’s the part that you just need to know beforehand. I don’t think it’s really intuitive, and so the chances of you just figuring it out during your interview are kind of slim.

Here’s how it works. Once you’ve got a hold of a node that’s inside the cycle, you can find the node at which the cycle begins by starting another pointer from the head of the linked list, and moving both pointers one step at a time. The point at which they meet is the node at which the cycle begins.

See? I told you it wasn’t intuitive.

Solution in Python

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next == None:
            return None

        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next

            assert slow != None
            slow = slow.next

            if fast == slow:
                break

        if fast == slow:
            slow2 = head

            while slow2 != slow:
                assert slow != None
                assert slow2 != None
                slow2 = slow2.next
                slow = slow.next

            return slow
        else:
            return None

Complexity

• Time: $O()$
  

• Space: $O()$
  

Mistakes I Made

And we are done.