Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.
There is a cycle in a linked list if at least one node in the list that can be visited again by following the next pointer.
Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it's next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.
Note: index is not given to you as a parameter.
Example 1:
Input: head = [1,2,3,4], index = 1
Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], index = -1
Output: false
Floyd's Cycle Detection Algorithm (also known as "tortoise and hare" algorithm) used in this code:¶
Two Pointers Concept:¶
- slow moves 1 step at a time
- fast moves 2 steps at a time
- Both start at the head of the linked list
Why It Works:¶
- If there's a cycle, fast will eventually catch up to slow inside the cycle
- Like a circular track where a faster runner laps a slower runner
- If there's no cycle, fast will reach the end (null)
- Time: O(n) - traverses the list once
- Space: O(1) - only uses two pointers
In [1]:
class ListNode:
def __init__(self,val=0,next=None):
self.val=val
self.next=next
def detectCycle(ll:ListNode):
slow,fast=ll,ll
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
return True
return False