Find Middle Element of Linked List in DSA Python - Build from Scratch

Find Middle Element of Linked List

📖 Scenario: Imagine you have a line of people waiting for a bus. You want to find the person standing exactly in the middle of the line.We will represent this line as a linked list, where each person is a node connected to the next.

🎯 Goal: Build a simple linked list with 5 nodes and find the middle node's value using a step-by-step approach.

📋 What You'll Learn

Create a linked list with exactly 5 nodes with values 10, 20, 30, 40, 50 in that order

Create a variable called slow and set it to the head of the linked list

Use a loop to move slow to the middle node by moving two pointers: slow moves one step, fast moves two steps

Print the value of the middle node stored in slow.data

💡 Why This Matters

🌍 Real World

Finding the middle element is useful in many real-world problems like splitting data, balancing tasks, or finding median values.

💼 Career

Understanding linked lists and pointer techniques is important for software engineering roles, especially those involving data structures and algorithms.

1

Create the linked list with 5 nodes

Create a class called Node with an __init__ method that takes data and sets self.data and self.next. Then create 5 nodes with values 10, 20, 30, 40, 50 and link them in order. Finally, create a variable called head that points to the first node.

DSA Python

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

Hint

Start by defining the Node class with data and next attributes. Then create each node and link them by setting the next attribute.

2

Set up pointers to find the middle

Create two variables called slow and fast and set both to head. These will help us find the middle node.

DSA Python

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

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)
node5 = Node(50)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1

# Set slow and fast pointers to head
# Your code here

Hint

Both slow and fast start at the beginning of the list.

3

Move pointers to find the middle node

Use a while loop that continues as long as fast and fast.next are not None. Inside the loop, move slow one step forward (slow = slow.next) and fast two steps forward (fast = fast.next.next).

DSA Python

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

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)
node5 = Node(50)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1

slow = head
fast = head

# Move slow by one and fast by two steps until fast reaches the end
# Your code here

Hint

Move slow one step and fast two steps in each loop until fast reaches the end.

4

Print the middle node's value

Print the value of the middle node by writing print(slow.data).

DSA Python

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

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)
node5 = Node(50)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

head = node1

slow = head
fast = head

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

# Print the middle node's data
# Your code here

Hint

The middle node's value is stored in slow.data. Print it to see the result.

Practice

1. What is the main idea behind finding the middle element of a singly linked list using the two-pointer technique?

easy

A. Use two pointers both moving one step at a time

B. Count all nodes first, then access the middle by index

C. Reverse the list and pick the first element

D. Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end

Solution

1. Step 1: Understand two-pointer movement

   The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

2. Step 2: Identify middle when fast pointer ends

   When the fast pointer reaches the end (null), the slow pointer will be at the middle node.

3. Final Answer:

   Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end -> Option D

4. Quick Check:

   Two-pointer technique = slow one step, fast two steps [OK]

Hint: Move fast pointer twice as fast as slow to find middle [OK]

Common Mistakes:

• Moving both pointers at the same speed
• Counting nodes first instead of using pointers
• Reversing the list unnecessarily

2. Which of the following Python code snippets correctly initializes pointers to find the middle of a linked list named head?

easy

A. slow = head\nfast = head

B. slow = head.next\nfast = head.next.next

C. slow = null\nfast = head

D. slow = head\nfast = null

Solution

1. Step 1: Initialize both pointers at head

   To start traversal, both slow and fast pointers should begin at the head node.

2. Step 2: Confirm correct initialization

   Setting slow = head and fast = head allows fast to move two steps and slow one step safely.

3. Final Answer:

   slow = head\nfast = head -> Option A

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head node [OK]

Common Mistakes:

• Starting slow or fast at null
• Starting fast pointer too far ahead
• Skipping initialization of pointers

3. What will be the output of the following code snippet that finds the middle element of a linked list?

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

# Creating linked list: 10 -> 20 -> 30 -> 40 -> 50
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)

print(find_middle(head))

medium

A. 30

B. 20

C. 40

D. 50

Solution

1. Step 1: Trace pointer movements

   Initially, slow=10, fast=10. After first loop: slow=20, fast=30. Second loop: slow=30, fast=50. Third loop ends as fast.next is null.

2. Step 2: Identify slow pointer value

   Slow pointer is at node with value 30 when loop ends, so 30 is middle.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Middle element = 30 [OK]

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

Common Mistakes:

• Returning fast pointer value instead of slow
• Off-by-one errors in loop condition
• Confusing node values during tracing

4. Identify the error in the following code that attempts to find the middle element of a linked list and fix it:

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

medium

A. Return fast.val instead of slow.val

B. Change loop condition to 'while fast and fast.next' to avoid NoneType errors

C. Initialize slow and fast to null instead of head

D. Remove the loop entirely and return head.val

Solution

1. Step 1: Analyze loop condition

   The condition 'while fast.next and fast.next.next' can cause an error if fast is null initially.

2. Step 2: Correct loop condition

   Changing it to 'while fast and fast.next' ensures fast is not null before accessing fast.next.

3. Final Answer:

   Change loop condition to 'while fast and fast.next' to avoid NoneType errors -> Option B

4. Quick Check:

   Safe loop condition = while fast and fast.next [OK]

Hint: Check fast pointer is not null before accessing next [OK]

Common Mistakes:

• Accessing fast.next without checking fast
• Returning wrong pointer's value
• Incorrect pointer initialization

5. Given a linked list with an even number of nodes, which node will the two-pointer method return as the middle?
For example, in the list 1 -> 2 -> 3 -> 4 -> null, what will be the middle element returned by the standard two-pointer approach?

hard

A. Node with value 2 (the first middle)

B. Node with value 1 (head node)

C. Node with value 3 (the second middle)

D. Node with value 4 (last node)

Solution

1. Step 1: Trace pointers on even-length list

   Start: slow=1, fast=1. Loop 1: slow=2, fast=3. Loop 2: fast tries to move two steps but reaches end, loop stops.

2. Step 2: Identify slow pointer position

   Slow pointer is at node with value 3 when loop ends, which is the second middle node.

3. Final Answer:

   Node with value 3 (the second middle) -> Option C

4. Quick Check:

   Two-pointer returns second middle in even list [OK]

Hint: Two-pointer method returns second middle in even-length lists [OK]

Common Mistakes:

• Assuming it returns first middle node
• Confusing head or last node as middle
• Not tracing pointer steps carefully