Common linked list patterns (runner technique) in Data Structures Theory - Mini Project: Build & Apply

Common linked list patterns (runner technique)

📖 Scenario: You are learning about linked lists, a way to store items where each item points to the next one. Sometimes, to solve problems faster, we use two pointers moving at different speeds. This is called the runner technique.Imagine you have a chain of train cars, and you want to find the middle car quickly. Using two runners, one moving twice as fast as the other, helps you find the middle without counting all cars first.

🎯 Goal: Build a simple linked list and use the runner technique to find the middle element of the list.

📋 What You'll Learn

Create a linked list with exactly 5 nodes containing values 10, 20, 30, 40, 50

Create two pointers called slow and fast starting at the head of the list

Move fast pointer two steps and slow pointer one step until fast reaches the end

Identify the middle node using the slow pointer

💡 Why This Matters

🌍 Real World

The runner technique helps quickly find the middle of a list or detect cycles without extra memory, useful in many software applications like navigation, scheduling, and data processing.

💼 Career

Understanding linked list patterns and the runner technique is important for software developers and engineers to write efficient code for data structures and algorithms.

1

Create the linked list with 5 nodes

Create a linked list by defining a Node class with value and next properties. Then create 5 nodes with values 10, 20, 30, 40, and 50 linked together starting from a variable called head.

Data Structures Theory

# Define Node class and create linked list nodes
# Your code here

Need a hint?

Start by defining a simple Node class. Then link nodes by setting the next property of each node to the next node.

2

Initialize the runner pointers

Create two variables called slow and fast and set both to point to the head of the linked list.

Data Structures Theory

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

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)

# Initialize slow and fast pointers
# Your code here

Need a hint?

Both pointers start at the beginning of the list, which is the head.

3

Move the pointers using the runner technique

Use a while loop to move fast two steps and slow one step forward until fast is None or fast.next is None. Use slow = slow.next and fast = fast.next.next inside the loop.

Data Structures Theory

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

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)

slow = head
fast = head

# Move slow and fast pointers using runner technique
# Your code here

Need a hint?

Keep moving fast two steps and slow one step until fast reaches the end.

4

Identify the middle node

After the loop ends, the slow pointer will be at the middle node. Assign the middle node's value to a variable called middle_value using middle_value = slow.value.

Data Structures Theory

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

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)

slow = head
fast = head

while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next

# Assign the middle node's value to middle_value
# Your code here

Need a hint?

The slow pointer now points to the middle node. Get its value.