Common linked list patterns (runner technique) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Runner Technique

In the runner technique for linked lists, two pointers move through the list at different speeds. What is the main purpose of using this technique?

A To sort the linked list using two pointers

B To reverse the linked list in place

C To find the middle of the linked list efficiently in one pass

D To delete nodes with a specific value

💡 Hint

Think about how moving pointers at different speeds can help locate a specific position in the list.

The runner technique uses a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. When the fast pointer reaches the end, the slow pointer is at the middle. This allows finding the middle in one pass.

📋 Factual

intermediate

Runner Technique Pointer Speeds

In the runner technique, if the fast pointer moves two nodes at a time, how many nodes does the slow pointer move per step?

A One node per step

B Two nodes per step

C Three nodes per step

D Zero nodes (it stays still)

💡 Hint

Consider the relative speeds of the two pointers.

The slow pointer moves one node at a time while the fast pointer moves two nodes at a time. This difference in speed is key to the technique.

🔍 Analysis

advanced

Detecting a Cycle Using Runner Technique

Given a linked list, which condition indicates that a cycle exists when using the runner technique with slow and fast pointers?

A Slow pointer reaches the end of the list

B Fast pointer and slow pointer meet at the same node

C Fast pointer reaches the end of the list (null)

D Slow pointer moves twice as fast as fast pointer

💡 Hint

Think about what happens if the list loops back on itself.

If the fast pointer ever equals the slow pointer, it means the list has a cycle. Otherwise, if the fast pointer reaches the end (null), there is no cycle.

🚀 Application

advanced

Finding the Start of a Cycle

After detecting a cycle in a linked list using the runner technique, what is the next step to find the node where the cycle begins?

A Move the fast pointer two nodes at a time until it reaches the cycle start

B Delete nodes until the cycle disappears

C Reverse the linked list to find the cycle start

D Reset the slow pointer to the head and move both pointers one node at a time until they meet

💡 Hint

After detection, think about how to locate the exact node where the cycle begins.

Once a cycle is detected, resetting the slow pointer to the head and moving both pointers one step at a time will cause them to meet at the cycle start node.

❓ Reasoning

expert

Why Runner Technique is Efficient

Why is the runner technique considered efficient for problems like finding the middle of a linked list or detecting cycles?

A It solves the problem in a single pass with constant extra space

B It uses extra memory to store nodes for quick access

C It requires sorting the linked list first

D It duplicates the linked list to compare nodes

💡 Hint

Think about time and space complexity when using two pointers.

The runner technique uses two pointers moving at different speeds to solve problems in one pass without extra memory, making it time and space efficient.

Practice

1. What is the main purpose of the runner technique in linked lists?

easy

A. To use two pointers moving at different speeds to solve problems efficiently

B. To sort the linked list elements in ascending order

C. To convert a linked list into an array

D. To delete all nodes from the linked list

Solution

1. Step 1: Understand the runner technique concept

   The runner technique involves two pointers moving through the list at different speeds to solve problems like finding the middle or detecting loops.

2. Step 2: Identify the main purpose

   This technique is used to efficiently solve linked list problems in one pass without extra memory.

3. Final Answer:

   To use two pointers moving at different speeds to solve problems efficiently -> Option A

4. Quick Check:

   Runner technique = two pointers at different speeds [OK]

Hint: Runner technique uses two pointers at different speeds [OK]

Common Mistakes:

• Thinking it sorts the list
• Confusing it with list conversion
• Assuming it deletes nodes

2. Which of the following is the correct way to initialize two pointers for the runner technique in a singly linked list?

easy

A. slow = head; fast = null

B. slow = head; fast = head.next

C. slow = null; fast = head

D. slow = head.next; fast = head

Solution

1. Step 1: Understand pointer initialization for runner technique

   Typically, slow pointer starts at head, and fast pointer starts at the next node to move faster.

2. Step 2: Check each option

   slow = head; fast = head.next correctly sets slow to head and fast to head.next, allowing fast to move two steps ahead.

3. Final Answer:

   slow = head; fast = head.next -> Option B

4. Quick Check:

   Fast pointer starts one step ahead [OK]

Hint: Fast pointer starts one node ahead of slow [OK]

Common Mistakes:

• Setting slow ahead of fast
• Starting pointers at null
• Both pointers starting at same node without offset

3. Consider the following linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null.
Using the runner technique where slow moves one step and fast moves two steps, what value will slow point to when fast reaches the end?

medium

A. 5

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace slow and fast pointers through the list

   Start: slow=1, fast=1
   Move 1: slow=2, fast=3
   Move 2: slow=3, fast=5
   Move 3: fast tries to move two steps but reaches null, stop.

2. Step 2: Identify slow pointer's position when fast ends

   When fast reaches the end (node 5), slow is at node 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Middle node = 3 [OK]

Hint: Slow pointer at middle when fast reaches end [OK]

Common Mistakes:

• Stopping too early and picking 2
• Assuming slow moves as fast as fast pointer
• Confusing node values with pointer positions

4. In the runner technique, if the fast pointer is not moving two steps but only one step each time, what problem might occur?

medium

A. The fast pointer will never reach the end, causing an infinite loop

B. The slow pointer will move too fast and skip nodes

C. The technique will still work correctly without issues

D. The slow pointer will become null immediately

Solution

1. Step 1: Understand the role of fast pointer speed

   The fast pointer moves two steps to catch up or reach the end faster than slow pointer.

2. Step 2: Analyze effect if fast moves only one step

   If fast moves one step, both pointers move at same speed, so fast never overtakes slow, possibly causing infinite loop in cycle detection.

3. Final Answer:

   The fast pointer will never reach the end, causing an infinite loop -> Option A

4. Quick Check:

   Fast pointer speed crucial to avoid infinite loops [OK]

Hint: Fast pointer must move faster to avoid infinite loops [OK]

Common Mistakes:

• Assuming slow pointer moves too fast
• Thinking technique works with equal speeds
• Ignoring infinite loop possibility

5. You want to detect if a linked list has a cycle using the runner technique. Which of the following best describes the condition to confirm a cycle?

hard

A. The slow pointer reaches the end of the list

B. The fast pointer becomes null

C. The slow and fast pointers meet at the same node

D. The slow pointer moves two steps at a time

Solution

1. Step 1: Recall cycle detection with runner technique

   If a cycle exists, fast pointer will eventually catch up to slow pointer inside the loop.

2. Step 2: Identify the condition for cycle detection

   The pointers meeting at the same node means the list has a cycle.

3. Final Answer:

   The slow and fast pointers meet at the same node -> Option C

4. Quick Check:

   Pointers meeting = cycle detected [OK]

Hint: Cycle detected when pointers meet [OK]

Common Mistakes:

• Thinking fast pointer reaching null means cycle
• Assuming slow pointer reaches end means cycle
• Confusing pointer speeds