Fast and slow pointers

Understand the idea

Fast/slow pointers exploit relative movement. For cycle detection, slow moves one link and fast two; inside a finite cycle their relative position advances modulo the cycle length.

Work through an example

In a two-node cycle, slow and fast eventually identify the same object. For a finite list, fast reaches None; equal stored values are irrelevant.

Time and space complexity

Cycle detection O(n) time/O(1) space. Midpoint search also uses O(n)/O(1).

Why it works

Both pointers stay on reachable nodes; if fast exits, no cycle exists.

Common mistakes

• Guard both fast and fast.next.
• Identity checks differ from value comparisons.

Chapter lab · Python implementation

A linked list stores values in nodes connected by references. The lab reverses links while retaining the next unread node. Draw references as arrows: changing a link does not move a node in memory. Ordered traversal is cheap; locating an arbitrary position still requires walking from a known node.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def reverse(head):
    previous=None
    current=head
    while current is not None:
        following=current.next
        current.next=previous
        previous,current=current,following
    return previous

def values(head):
    output=[]
    while head is not None:
        output.append(head.value)
        head=head.next
    return output

def has_cycle(head):
    slow=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

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

head=Node(1,Node(2,Node(3)))
assert values(reverse(head))==[3,2,1]
assert reverse(None) is None
assert not has_cycle(Node(1))
a=Node(1); b=Node(2,a); a.next=b; assert has_cycle(a)