Common linked list patterns (runner technique) in Data Structures Theory - Full Explanation

Introduction

Working with linked lists can be tricky because you only move forward one step at a time. The runner technique helps solve problems where you need to compare or find elements at different speeds or positions in the list.

Explanation

Basic idea of the runner technique

The runner technique uses two pointers moving through the list at different speeds or starting points. One pointer moves faster or ahead, while the other moves slower or behind. This helps find relationships between nodes without extra memory.

Two pointers moving at different speeds or positions help solve linked list problems efficiently.

Finding 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. This works because the fast pointer covers twice the distance.

The slow pointer ends at the middle when the fast pointer reaches the list end.

Detecting a cycle in a linked list

Using the same slow and fast pointers, if the list has a cycle, the fast pointer will eventually catch up to the slow pointer inside the loop. If the fast pointer reaches the end, there is no cycle.

Pointers meeting inside the list means a cycle exists.

Finding the start of a cycle

After detecting a cycle, reset one pointer to the list start. Move both pointers one step at a time. Where they meet again is the start of the cycle. This works because the distance from the start to the cycle equals the distance from the meeting point to the cycle start.

Moving pointers at the same speed after detection finds the cycle start.

Finding the nth node from the end

Move one pointer n steps ahead, then move both pointers one step at a time. When the first pointer reaches the end, the second pointer is at the nth node from the end. This avoids counting the list length first.

Advancing one pointer ahead by n steps helps find the nth node from the end.

Real World Analogy

Imagine two runners on a track. One runs faster and the other slower. By watching where they meet or how far apart they are, you can learn about the track's length or if it loops back on itself.

Basic idea of the runner technique → Two runners running at different speeds on the same track

Finding the middle of a linked list → The slower runner reaching halfway when the faster runner finishes the race

Detecting a cycle in a linked list → The faster runner catching up to the slower runner if the track loops

Finding the start of a cycle → Both runners starting together again to find the loop's start point

Finding the nth node from the end → One runner starting ahead by n steps, then both running together to find a position

Diagram

Diagram

┌───────────────┐
│ Linked List    │
│               │
│  o → o → o → o → o → o → o → null
│       ↑       ↑
│      slow    fast
└───────────────┘

Diagram showing two pointers (slow and fast) moving through a linked list at different speeds.

Key Facts

Runner technique → A method using two pointers moving at different speeds or positions to solve linked list problems.

Slow pointer → Pointer that moves one step at a time in the linked list.

Fast pointer → Pointer that moves two steps at a time in the linked list.

Cycle detection → If fast and slow pointers meet inside the list, a cycle exists.

Middle node → The node where the slow pointer stops when the fast pointer reaches the end.

Nth node from end → Found by advancing one pointer n steps ahead, then moving both until the first reaches the end.

Code Example

Data Structures Theory

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def find_middle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.val

# Create linked list: 1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

print(find_middle(head))

Common Confusions

Believing the slow pointer always points exactly to the middle in even-length lists.

Believing the slow pointer always points exactly to the middle in even-length lists. In even-length lists, the slow pointer stops at the first of the two middle nodes, not exactly the center.

Assuming cycle detection works if pointers never meet immediately.

Assuming cycle detection works if pointers never meet immediately. Pointers may take several steps before meeting inside a cycle; immediate meeting is not required.

Thinking the fast pointer moves twice as fast in terms of time, not steps.

Thinking the fast pointer moves twice as fast in terms of time, not steps. The fast pointer moves two nodes per step, not necessarily twice as fast in real time.

Summary

The runner technique uses two pointers moving at different speeds to solve linked list problems efficiently.

It helps find the middle node, detect cycles, find cycle starts, and locate nodes from the end without extra memory.

Understanding how slow and fast pointers move and meet is key to applying this technique correctly.

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