Loop in a Chain
Problem
You receive the head of a singly linked chain of nodes. Somewhere a node may point back to an earlier node, which makes the walk go round forever instead of reaching the end. Return True if the chain contains such a loop and False if following the links eventually reaches None. In the examples the chain is described by its values plus pos, the index the last node links back to, or -1 for no loop.
Examples
Input: values = [3, 2, 0, -4], pos = 1
Output: True
Why: the last node links back to the node holding 2Input: values = [1, 2], pos = -1
Output: False
Why: the walk ends after the second nodeInput: values = [7], pos = 0
Output: True
Why: edge case, a single node that points to itselfHints
0 / 3
Remembering every node you visit works, but it costs memory for the whole chain. Is there a way to notice a loop without storing anything?
Picture two runners on a track, one twice as fast as the other. On a straight road they never meet again; on a circular one they must.
Move one pointer one step at a time and another two steps at a time. If the fast one runs off the end there is no loop; if the two ever land on the same node, there is one.
Solution
Two pointers start at the head, one moving one link per step and the other moving two. Without a loop the fast pointer reaches the end and the answer is False. With a loop both pointers eventually circle inside it, and since the gap between them shrinks by one link every step, the fast pointer must land exactly on the slow one. Time is O(n) and space is O(1).
class Node:
def __init__(self, val): self.val, self.next = val, None
def build(values, pos): # the tail links back to index pos, or nowhere if -1
nodes = [Node(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
def has_loop(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next # the gap closes by one link per step
if slow is fast:
return True
return False # the fast pointer found the end
print(has_loop(build([3, 2, 0, -4], 1))) # -> True
print(has_loop(build([1, 2], -1))) # -> False
print(has_loop(build([7], 0))) # -> TrueStuck on the idea rather than the code? Detect a Cycle covers it.