Linked List Cycle II

Problem Summary

• Given a linked list return the first node where the cycle begins else if no cycle return None

What is Being Asked?

• Find cycle and return first node where it starts

Key Observations

• Solve it in $O(1)$ space complexity

Approach Taken

• Fast & Slow Pointers to find the cycle then start again at the start and iterate slow and this new pointer until they meet.
• They will meet at the beginning

Main Concepts Used

• Fast & Slow Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each item once
• Space: $O(1)$ → Reason: Not storing a copy

Code

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                # cycle detected, restart
                walker = head
                while slow != walker:
                    walker = walker.next
                    slow = slow.next
                return walker
        return None

Alternative Solution

• Find the length of the cycle
• Move len(cycle) ahead from head
• Iterate walker and this above pointer until they meet
  Details