Linked List Cycle Detection
Problem Statement
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 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
Constraints:
1 <= Length of the list <= 1000
.-1000 <= Node.val <= 1000
index
is-1
or a valid index in the linked list.
You should aim for a solution with O(n)
time and O(1)
space, where n
is the length of the given list.
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(1)
space, where n
is the length of the given list.
Hint 1
A naive approach would be to use a hash set, which takes O(1)
time to detect duplicates. Although this solution is acceptable, it requires O(n)
extra space. Can you think of a better solution that avoids using extra space? Maybe there is an efficient algorithm which uses two pointers.
Hint 2
We can use the fast and slow pointers technique, which is primarily used to detect cycles in a linked list. We iterate through the list using two pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If the list has a cycle, these two pointers will eventually meet. Why does this work?
Hint 3
When there is no cycle in the list, the loop ends when the fast pointer becomes null
. If a cycle exists, the fast pointer moves faster and continuously loops through the cycle. With each step, it reduces the gap between itself and the slow pointer by one node. For example, if the gap is 10
, the slow pointer moves by 1
, increasing the gap to 11
, while the fast pointer moves by 2
, reducing the gap to 9
. This process continues until the fast pointer catches up to the slow pointer, confirming a cycle.
Solution
Hash Set
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = next
def has_cycle(head: Optional[ListNode]) -> bool: seen = set() cur = head while cur: if cur in seen: return True seen.add(cur) cur = cur.next return False
Time complexity: O(n)
Space complexity: O(n)
Fast And Slow Pointers
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = next
def has_cycle(head: Optional[ListNode]) -> bool: slow, fast = head, head
while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
Time complexity: O(n)
Space complexity: O(1)