Exercise 2 solution

    class Node:
        def __init__(self, value, next=None):
            self.value = value
            self.next = next

    def build(values):
        head = None
        for v in reversed(values):
            head = Node(v, head)
        return head

    def has_cycle(head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

    h = build([1, 2, 3, 4])
    print(has_cycle(h))
    tail = h
    while tail.next:
        tail = tail.next
    tail.next = h.next          # the last node points back to the second
    print(has_cycle(h), has_cycle(None))

Output:
    False
    True False

If there is a loop, the fast pointer eventually laps the slow one and they
meet; if there is not, fast reaches None. The comparison uses "is" (same
node object), not "==", because two different nodes can hold equal values.
It needs only two variables, whereas remembering every visited node in a
set would work too but use memory proportional to the list length.