Common linked list patterns (runner technique) in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the slow pointer at the head of the linked list.

Data Structures Theory

slow = [1]

Drag options to blanks, or click blank then click option'

Afast

Btail

CNone

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Starting slow at tail or None instead of head.

Confusing slow with fast pointer initialization.

The slow pointer starts at the head of the linked list to begin traversal.

2fill in blank

medium

Complete the code to move the fast pointer two steps ahead in the linked list.

Data Structures Theory

fast = fast[1]next[2]next

Drag options to blanks, or click blank then click option'

A.

B->

C=>

D::

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect operators like '->' or '=>' which are not valid in this context.

Moving only one step instead of two.

In many programming languages, the dot operator is used to access the next node in a linked list.

3fill in blank

hard

Fix the error in the loop condition to ensure the fast pointer and its next node are valid.

Data Structures Theory

while fast != None and fast[1]next != None:

Drag options to blanks, or click blank then click option'

A=>

B->

C.

D::

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect operators like '->' or '=>' which cause syntax errors.

Not checking fast.next leading to runtime errors.

The dot operator is used to access the 'next' attribute of the fast pointer node.

4fill in blank

hard

Fill both blanks to correctly advance slow by one step and fast by two steps in the loop.

Data Structures Theory

slow = slow[1]next
fast = fast[2]next[3]next

Drag options to blanks, or click blank then click option'

A.

B->

C::

D=>

Attempts:

3 left

💡 Hint

Common Mistakes

Using different operators inconsistently.

Advancing fast only one step instead of two.

Use the dot operator to access the next nodes for both slow and fast pointers.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps each node's value to its position if the value is even.

Data Structures Theory

result = [1]: [2] for [3], [1] in enumerate(nodes) if [1] % 2 == 0

Drag options to blanks, or click blank then click option'

Aindex

Bvalue

Cfor

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up keys and values in the dictionary comprehension.

Using incorrect loop variable names.

The comprehension maps each value to its index if the value is even. {value: index for index, value in enumerate(nodes) if value % 2 == 0}

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