Return true if the linked list contains a cycle (some node's Next points back to an
earlier node).
hasCycle(head)
Input format: values | pos, where values are the node values and pos is the
0-based index of the node that the tail's Next links back to, or -1 for no cycle.
values=3 2 0 -4, pos=1 // → true (tail links to index 1)
values=1 2, pos=0 // → true
values=1 2 3, pos=-1 // → false
A cycle means some node's next loops back to an earlier node instead of reaching the end. Walking with a single pointer looking for null would loop forever on a cyclic list — you need to detect "I've been here before" without infinite looping, ideally without extra memory.
Remember every visited node in a set, checking before each move. Correct, but costs O(n) memory — not ideal for a very long list.
Use two pointers at different speeds: slow advances one node, fast advances two. On a straight track (no cycle), the fast runner just reaches the end and stops. On a looping track (a cycle), both runners keep going forever, and since fast gains one extra step of relative distance every iteration, it's guaranteed to eventually lap the slow runner.
Once both pointers are in the cyclic portion, the gap between them shrinks by exactly one each iteration (fast gains two steps, slow gains one). A shrinking gap on a finite loop must hit zero — the two pointers must land on the same node. Guaranteed, not probabilistic.
For an acyclic list, the fast pointer (or the node after it) eventually becomes null, since it races toward the real end twice as fast. So: fast or its next hitting null means no cycle; the two pointers landing on the same node means there is one.
Only two extra pointers — O(1) space — versus O(n) for the visited-set approach, while still O(n) time overall (fast traverses the list at most twice before finishing or meeting slow). The standard example of trading a bit of clever bookkeeping for a big memory win.
def has_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.