1. Concept library
  2. Data Structures & Algorithms
  3. Module 4: Linked lists

Concept

Fast and slow pointers

Two pointers move through a list at different speeds. If there is a cycle the fast one laps the slow one; otherwise when the fast one reaches the end the slow one is at the middle.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain why a fast pointer laps a slow one in a cycle
  2. Find the middle of a list in one pass
  3. Spot the missing fast.next check that fails on even-length lists

In practice

A few lines that show Fast and slow pointers doing its job.

Python
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

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

The common mistake

Watch for

Checking only fast and not fast.next before advancing two steps. On an even-length list fast becomes None one step early and fast.next.next raises AttributeError.

What to know first

Your roadmap puts these before Fast and slow pointers, unless you already know them.

How it stays learned

Once a session shows you understand Fast and slow pointers, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Next in the moduleReversing a list →