Detect whether a linked list is circular
Filed under Amazon
Free read 2 of 3Ask whether the list may be empty, contain duplicate values, and whether you may modify nodes. Compare nodes by identity, not value.
The question
Given the head of a singly linked list, determine whether the list is circular, that is, whether some node can be reached again by following next pointers (the list contains a cycle). Return true if there is a cycle, otherwise false. Be prepared for follow-up questions such as finding where the cycle begins or its length, and for the space/time trade-offs of your approach.
Constraints
- 0 <= number of nodes <= 10^5
- Node values may repeat
- Solve with O(1) extra space if possible
Examples
- Input
- list = 3 -> 2 -> 0 -> -4, with the tail linked back to the node with value 2
- Output
- true
- Why
- Following next pointers from -4 returns to 2, so there is a cycle.
- Input
- list = 1 (tail points to nothing)
- Output
- false
- Why
- The traversal ends at null.
Approach
Ask whether the list may be empty, contain duplicate values, and whether you may modify nodes. Compare nodes by identity, not value.
Store visited nodes in a hash set; if a node repeats there is a cycle. O(n) time, O(n) space.
Advance slow by one and fast by two. If fast reaches the end there is no cycle; if they meet, there is one. O(n) time, O(1) space.
Empty list, single node pointing to itself, two nodes. For the cycle start, reset one pointer to head after the meeting and move both by one; for the length, loop once from the meeting node.
Solution
O(n) time, O(1) space
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_list(values, pos):
"""Build a linked list; if pos >= 0 the tail links back to node index pos."""
nodes = [ListNode(v) for v in values]
for a, b in zip(nodes, nodes[1:]):
a.next = b
if nodes and pos >= 0:
nodes[-1].next = nodes[pos]
return nodes[0] if nodes else None
class Solution:
def hasCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
Tips
- What they are testing: Knowledge of Floyd's cycle detection and the ability to compare it with a hash set approach.
- Common mistake: Comparing node values instead of node identity, or dereferencing fast.next.next without checking fast and fast.next for None.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.