Common linked list patterns (runner technique) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Common linked list patterns (runner technique)

Start: Initialize two pointers

↓

Set slow = head, fast = head

↓

Move fast pointer twice as fast as slow

↓

Check if fast or fast.next is None?

Yes→Stop: End of list reached

No↓

Move slow by one step, fast by two steps

↓

Repeat until fast reaches end

↓

Use slow pointer position for desired operation

The runner technique uses two pointers moving at different speeds to traverse a linked list, enabling efficient detection of midpoints, cycles, or other patterns.

Execution Sample

Data Structures Theory

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

This code finds the middle node of a linked list by moving 'fast' pointer twice as fast as 'slow'.

Analysis Table

Step	slow Pointer	fast Pointer	Condition fast and fast.next	Action	List State (Nodes)
1	Node1	Node1	True	Move slow to Node2, fast to Node3	Node1 -> Node2 -> Node3 -> Node4 -> Node5
2	Node2	Node3	True	Move slow to Node3, fast to Node5	Node1 -> Node2 -> Node3 -> Node4 -> Node5
3	Node3	Node5	False	Stop loop	Node1 -> Node2 -> Node3 -> Node4 -> Node5
Exit	-	-	fast or fast.next is None	Loop ends, slow at middle Node3	Middle node found at Node3

💡 fast reached the end of the list (Node5), so condition fast and fast.next is False, loop stops.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3 (End)
slow	Node1	Node2	Node3	Node3
fast	Node1	Node3	Node5	Node5

Key Insights - 3 Insights

Why does the loop stop when fast or fast.next is None?

Because fast moves two steps at a time, if fast or fast.next is None, it means we've reached the end or there is no next node to jump to, so continuing would cause an error. See execution_table row 3.

Why do we move slow by one step but fast by two steps?

Moving fast twice as fast allows slow to reach the middle when fast reaches the end. This difference in speed helps find the midpoint efficiently, as shown in execution_table steps 1 and 2.

What if the list has an even number of nodes? Where does slow end?

In an even-length list, slow will stop at the first of the two middle nodes because the loop condition fails when fast or fast.next is None. This is consistent with the stopping condition in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, where is the slow pointer?

A Node3

B Node2

C Node5

D Node1

💡 Hint

Check the 'slow Pointer' column at Step 2 in the execution_table.

At which step does the loop condition become false?

A Step 3

B Step 2

C Step 1

D Exit

💡 Hint

Look at the 'Condition fast and fast.next' column in execution_table where it changes to False.

If fast moved only one step each time instead of two, how would the slow pointer's position change at Step 2?

A It would be at Node3

B It would be at Node2

C It would be at Node4

D It would be at Node5

💡 Hint

Consider that slow moves one step per iteration and fast moves one step instead of two; slow would advance more slowly relative to fast.

Concept Snapshot

Runner Technique for Linked Lists:
- Use two pointers: slow and fast
- Move slow by 1 step, fast by 2 steps
- Loop until fast or fast.next is None
- Slow ends at middle node (or near middle)
- Useful for finding midpoints, detecting cycles

Full Transcript

The runner technique uses two pointers moving at different speeds through a linked list. Initially, both pointers start at the head. In each loop iteration, the slow pointer moves one node forward, while the fast pointer moves two nodes forward. The loop continues as long as the fast pointer and its next node exist. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. This method efficiently finds the midpoint of the list without needing to know its length in advance. The execution table shows step-by-step how slow and fast pointers move through the nodes, and the variable tracker records their positions after each step. Key moments clarify why the loop stops and why the pointers move at different speeds. The visual quiz tests understanding of pointer positions and loop conditions. This technique is a common pattern in linked list problems.

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