Linked lists · stretch

Does it loop?

Some lists loop: the last node's next points back into the list, so walking it never ends. Write has_cycle(head) returning True if it loops.

Use two walkers: slow moves one node at a time, fast two. If there is a loop, fast eventually laps slow and they meet.

right answers
arguments left as they should be
without id, set

Already written for you — you can use these

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5 
6def build(values):
7    head = None
8    for v in reversed(values):
9        head = Node(v, head)
10    return head

def has_cycle(head):
    node = head
    while node is not None:
        node = node.next
    return False

Run adds print(has_cycle(build([1, 2, 3]))) after your code, to try it.

Stuck on the idea rather than the code? The Linked lists lesson walks through it.