LESSON 3 · PATTERN GUIDE

Fast/Slow Pointers (Linked List)

Move two linked-list references at different speeds to detect cycles or locate a middle position.

FIRST, LEARN THE PATTERNAdvance slow by one node and fast by two. If a cycle exists, fast eventually catches slow; if the list ends, slow is near the midpoint.

The task asks about a cycle, midpoint, kth-from-end node, or a linked-list position without knowing the length first.

How to approach it

Use a null check before fast advances twice. For kth-from-end, keep a lead pointer k nodes ahead, then move both together.

Watch out for

Define behavior for empty lists, one-node lists, and whether the requested position is counted from zero or one.

A CLOSER EXPLANATION

The speed difference creates useful information without counting every node first. If fast reaches null, the list is finite; if fast and slow meet, the path loops. To find the cycle entrance, reset one pointer to the head after the meeting and move both one step at a time.

NOW YOU TRY

Practice question

A linked list has 7 nodes. Using slow-by-one and fast-by-two, which node does slow reach when fast reaches the end?

EXAMPLEList: A → B → C → D → E → F → G → nullGive your answer before revealing the explanation.

Show a hint

Each fast-pointer move covers two nodes while slow advances one.

Show an answer

D, the middle node.

CONNECT IT TO REAL LIFE

Fast/Slow Pointers (Linked List) at work

A music playlist stores each track's next-track link. The last track accidentally links back to track 3. How can you detect the loop without storing every track ID?

Show one possible approach

Start slow and fast at the first track. Advance slow by one link and fast by two; if they meet, a cycle exists. This uses constant extra space.

Practice next

Use these problem IDs to find additional practice for this pattern:

14114219876160234