Find Middle Element of Linked List in DSA Python - Execution Trace

Concept Flow - Find Middle Element of Linked List

Start at head

↓

Initialize two pointers: slow, fast

↓

Check: fast != None and fast.next != None?

No→slow is middle

Yes↓

Move slow by 1 node

↓

Move fast by 2 nodes

↓

Repeat check

Use two pointers moving at different speeds; when fast reaches end, slow is at middle.

Execution Sample

DSA Python

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

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
print(slow.data)

Find middle node by moving slow pointer one step and fast pointer two steps until fast reaches end.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Linked List State	Pointer Movement Description
1	Initialize pointers	Node(10)	Node(10)	10 -> 20 -> 30 -> 40 -> 50 -> null	slow and fast start at head (10)
2	Check condition	Node(10)	Node(10)	10 -> 20 -> 30 -> 40 -> 50 -> null	fast and fast.next not null, continue
3	Move pointers	Node(20)	Node(30)	10 -> 20 -> 30 -> 40 -> 50 -> null	slow moves to 20, fast moves to 30
4	Check condition	Node(20)	Node(30)	10 -> 20 -> 30 -> 40 -> 50 -> null	fast and fast.next not null, continue
5	Move pointers	Node(30)	Node(50)	10 -> 20 -> 30 -> 40 -> 50 -> null	slow moves to 30, fast moves to 50
6	Check condition	Node(30)	Node(50)	10 -> 20 -> 30 -> 40 -> 50 -> null	fast.next is None, stop loop
7	Result	Node(30)	Node(50)	10 -> 20 -> 30 -> 40 -> 50 -> null	slow is at middle node with data 30

💡 fast reached end or fast.next is None, slow pointer is at middle node

Variable Tracker

Variable	Start	After Step 3	After Step 5	Final
slow	Node(10)	Node(20)	Node(30)	Node(30)
fast	Node(10)	Node(30)	Node(50)	Node(50)

Key Moments - 3 Insights

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

Moving fast pointer two steps allows it to reach the end twice as fast as slow. When fast reaches the end, slow is exactly at the middle. See execution_table rows 3 and 5 for pointer movements.

What happens if the list has even number of nodes?

The slow pointer will stop at the second of the two middle nodes. This is because the loop stops when fast or fast.next is None. The code can be adjusted if the first middle is needed.

Why do we check both fast and fast.next in the loop condition?

Checking fast.next ensures we don't get an error when trying to move fast two steps. If fast.next is None, moving two steps is impossible. See execution_table rows 2, 4, and 6 for condition checks.

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer pointing to after step 5?

A Node with data 20

B Node with data 30

C Node with data 50

D Node with data 40

💡 Hint

Check the 'slow Pointer Node' column at step 5 in execution_table.

At which step does the loop condition become false?

A Step 6

B Step 7

C Step 4

D Step 3

💡 Hint

Look at the 'Check condition' rows and see when fast.next is None in execution_table.

If the linked list had 6 nodes instead of 5, where would the slow pointer stop?

A At node 2 (second node)

B At node 3 (third node)

C At node 4 (fourth node)

D At node 5 (fifth node)

💡 Hint

Think about how slow moves one step and fast moves two steps; slow stops at second middle in even length lists.

Concept Snapshot

Find middle node by using two pointers:
- slow moves 1 step at a time
- fast moves 2 steps at a time
- loop until fast or fast.next is None
- slow pointer then points to middle node
- works for odd and even length lists (stops at second middle for even)

Full Transcript

To find the middle element of a linked list, we use two pointers starting at the head. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. We continue moving them until the fast pointer reaches the end or has no next node. At this point, the slow pointer will be at the middle node. This method works efficiently in one pass without knowing the list length. For example, in a list 10 -> 20 -> 30 -> 40 -> 50, slow moves through 10, 20, 30 while fast moves through 10, 30, 50. When fast reaches 50 and cannot move further, slow is at 30, the middle node.

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