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.