Linked List Interview Questions: Fast and Slow Pointers Explained

Fast and slow pointers solve linked list problems in linear time with constant space. You move one pointer one step at a time and another two steps at a time to find structural properties without extra memory.

The Core Mechanism

Imagine a race track. Two runners start at the same point. One runs at normal speed, the other at double speed. If the track is a straight line, the fast runner finishes first. If the track is a loop, the fast runner laps the slow one and they meet. This is the physical intuition behind Floyd's algorithm.

In code, you initialize slow and fast to the head of the list. You advance slow by one node and fast by two nodes in a loop. If fast hits null, there is no cycle. If fast equals slow, a cycle exists. This check takes O(n) time and O(1) space. You do not need a hash set to track visited nodes.

Detecting the Cycle Start

Finding where the cycle begins is trickier. Once you detect a meeting point, reset one pointer to the head. Keep the other at the meeting point. Move both one step at a time. They will meet again at the start of the cycle.

Why does this work? Let the distance from the head to the cycle start be a. Let the distance from the cycle start to the meeting point be b. Let the distance from the meeting point back to the cycle start be c. The cycle length is b + c.

When they meet, the slow pointer has traveled a + b. The fast pointer has traveled a + b + k(b + c) for some integer k. Since fast moves twice as fast, 2(a + b) = a + b + k(b + c). Simplifying gives a + b = k(b + c). This means a = (k - 1)(b + c) + c.

If you reset one pointer to the head and move both one step at a time, the pointer from the head travels a steps to reach the cycle start. The pointer from the meeting point travels c steps to reach the cycle start, then loops around k - 1 times. They meet exactly at the cycle start. This math holds for any cycle length.

Finding the Middle

To find the middle of a list, use the same pointers. Start both at the head. Move slow one step and fast two steps. When fast reaches the end, slow is at the middle.

Consider a list with 5 nodes: 1 -> 2 -> 3 -> 4 -> 5. Step 1: slow at 2, fast at 3. Step 2: slow at 3, fast at 5. fast is at the last node. slow is at index 2, which is the middle.

If the list has 4 nodes: 1 -> 2 -> 3 -> 4. Step 1: slow at 2, fast at 3. Step 2: slow at 3, fast at null. slow is at index 2. For even-length lists, this is the second middle node. This is standard for problems like "Reorder List".

Palindrome Check

To check if a list is a palindrome, you need to compare the first half with the reversed second half.

1. Find the middle using fast-slow pointers.
2. Reverse the second half.
3. Compare the first half with the reversed second half.
4. Reverse the second half again to restore the list (if required).

Example: 1 -> 2 -> 3 -> 2 -> 1. Middle is 3. Reverse second half: 1 -> 2 -> 3 -> 2 -> 1 becomes 1 -> 2 -> 3 -> 2 <- 1. Compare: 1==1, 2==2. It is a palindrome. This takes O(n) time. You traverse the list three times: once to find middle, once to reverse, once to compare.

Reorder List

Problem: Reorder L0 -> L1 -> ... -> Ln to L0 -> Ln -> L1 -> Ln-1 -> ....

1. Find middle.
2. Reverse second half.
3. Merge first half and reversed second half alternately.

Input: 1 -> 2 -> 3 -> 4. Middle: 3. Reverse second half: 3 -> 4 becomes 4 -> 3. Merge: Take 1 from first, 4 from second. Take 2 from first, 3 from second. Result: 1 -> 4 -> 2 -> 3.

This approach avoids using arrays. Storing the list in an array takes O(n) space. The pointer technique keeps it at O(1).

Why This Matters

Interviewers ask these questions because they test your ability to manipulate pointers and reason about state without auxiliary data structures. You cannot just copy the code. You must understand why the pointers meet where they do.

If you get stuck, draw the list on paper. Mark the positions of slow and fast at each step. Count the steps. Verify the math. This visual check prevents off-by-one errors.

The technique applies to any linear structure where you need to find a relative position or detect a loop. It is a fundamental tool in your toolkit.

Practice these four problems: Detect Cycle, Find Cycle Start, Middle of List, Palindrome List. Solve them without looking at the solution. Then, try to explain the math of the cycle start detection to a friend. If you can derive a = (k - 1)(b + c) + c from scratch, you understand the concept.

Go to DSA Tracker and solve the "Linked List Cycle" problem set. Start with the detection, then move to the start point. Do not skip the derivation.