Skip to content
CodeItRaw
Linked Lists

Lesson 2/4

How do you find the middle of a chain without knowing its length? Use two pointers: let the slow one take one step a turn and the fast one two. When the fast one reaches the end the slow one has come exactly half way. One pass, no counter.

slow = fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
return slow
Both parts of the condition are needed: to write fast.next.next both fast and fast.next must exist. With an even number of nodes this loop stops at the second of the two middles.

Trace a small chain on paper: in 1 → 2 → 3 → 4 → 5 the slow one stops at 3; in 1 → 2 → 3 → 4 it stops at 3 again. If you want the first middle you cut the condition one step earlier (by asking whether fast.next and fast.next.next exist).

Tasks

Tasks open in order. Solve them all and the next lesson opens.

This lesson's tasks open when the lessons before it are finished. You can read the explanation now.

  1. 01

    Fast and Slow

    Code reading · Predict the Output

  2. 02

    Dead Center

    Function

If you would rather not wait for the order, every problem is open without locks: Problem list