Common linked list patterns (runner technique) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the runner technique in linked lists?

The runner technique uses two pointers moving at different speeds through a linked list to solve problems efficiently, like detecting cycles or finding the middle node.

beginner

How does the runner technique help find the middle of a linked list?

One pointer moves one step at a time (slow), and the other moves two steps at a time (fast). When the fast pointer reaches the end, the slow pointer is at the middle.

beginner

What problem can the runner technique detect in a linked list?

It can detect cycles (loops) by moving one pointer faster than the other. If they meet, a cycle exists.

intermediate

Why is the runner technique efficient?

It solves problems in a single pass through the list, using two pointers, which saves time and memory compared to multiple passes.

beginner

Give a real-life analogy for the runner technique.

Imagine two friends walking on a path: one walks slowly, the other runs faster. When the faster friend reaches the end, the slower friend is halfway along the path.

What does the fast pointer do in the runner technique?

A Moves two steps at a time

B Moves one step at a time

C Stays still

D Moves three steps at a time

The fast pointer moves two steps at a time to help find the middle or detect cycles.

If the fast and slow pointers meet in a linked list, what does it indicate?

A The list has only one node

B The list is empty

C There is a cycle in the list

D The list is sorted

Meeting of fast and slow pointers means the list has a cycle (loop).

What is the main advantage of using the runner technique?

A Uses extra memory

B Requires multiple passes

C Only works on arrays

D Solves problems in one pass efficiently

The runner technique solves problems in a single pass, making it efficient.

Which problem is NOT typically solved by the runner technique?

A Sorting the linked list

B Finding the middle node

C Detecting cycles

D Checking if the list is empty

Sorting is not solved by the runner technique; it focuses on traversal and detection.

In the runner technique, when does the slow pointer reach the middle?

A When the list is empty

B When the fast pointer reaches the end

C When both pointers start

D When the slow pointer reaches the end

The slow pointer is at the middle when the fast pointer reaches the end.

Explain how the runner technique works to find the middle of a linked list.

Think about two friends walking at different speeds on a path.

Describe how the runner technique can detect a cycle in a linked list.

Imagine two runners on a circular track.