imashutosh51

Linked List loop detection

Mar 25th, 2026 (edited)
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.08 KB | None | 0 0
  1. Proof:
  2. ---------o
  3. suppose circle distance=C
  4. suppose entry of LL to cycle starting point=x
  5. first collision happened point=K
  6. distance bw k-> entry of the cycle=y
  7. 2*slow=fast
  8. 2*(c-y+x)=x+c+c-y (One circle already completed by the fast pointer)
  9. 2c-2y+2x=x+2c-y
  10. x=y so after the first collision of slow & fast, both starts moving one step so x=y & x is the distance of starting of LL to the cycle entry point.
  11. ***Move fast only when you can move two nodes***
  12. class Solution:
  13.     def hasCycle(self, head: Optional[ListNode]) -> bool:
  14.         slow=head
  15.         fast=head
  16.         while fast and fast.next: #move the fast only if you can move two nodes
  17.             slow=slow.next
  18.             fast=fast.next.next
  19.             if slow==fast:
  20.                 break
  21.         if not fast or fast.next==None: #check if fast==None or fast.next==None because in previous while, even fast.next=None, we considered not a cycle and didn't move
  22.             return False
  23.         slow=head
  24.         while fast and slow!=fast:
  25.             slow=slow.next
  26.             fast=fast.next
  27.         return slow.val
Advertisement
Add Comment
Please, Sign In to add comment