Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Proof:
- ---------o
- suppose circle distance=C
- suppose entry of LL to cycle starting point=x
- first collision happened point=K
- distance bw k-> entry of the cycle=y
- 2*slow=fast
- 2*(c-y+x)=x+c+c-y (One circle already completed by the fast pointer)
- 2c-2y+2x=x+2c-y
- 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.
- ***Move fast only when you can move two nodes***
- class Solution:
- def hasCycle(self, head: Optional[ListNode]) -> bool:
- slow=head
- fast=head
- while fast and fast.next: #move the fast only if you can move two nodes
- slow=slow.next
- fast=fast.next.next
- if slow==fast:
- break
- 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
- return False
- slow=head
- while fast and slow!=fast:
- slow=slow.next
- fast=fast.next
- return slow.val
Advertisement
Add Comment
Please, Sign In to add comment