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

Concept Flow - Find Middle Element of Linked List

Start: head points to first node

↓

Initialize two pointers: slow and fast at head

↓

Loop: fast != NULL and fast->next != NULL?

No→Stop

Yes↓

Move slow by 1 node

↓

Move fast by 2 nodes

↓

Repeat loop

↓

slow now points to middle node

↓

Return slow->data as middle element

Use two pointers moving at different speeds to find the middle node in one pass.

Execution Sample

DSA C

struct Node {
  int data;
  struct Node* next;
};

int findMiddle(struct Node* head) {
  struct Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow->data;
}

This code finds the middle element of a linked list using slow and fast pointers.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Visual State
1	Initialize slow and fast at head	Node(10)	Node(10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → ∅ │ next:──┼──→│ next:──┼──→│ next:──┼──→│ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
2	Check fast and fast->next (fast=10, fast->next=20) - continue	Node(10)	Node(10)	Same as step 1
3	Move slow by 1 (slow=20), fast by 2 (fast=30)	Node(20)	Node(30)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → ∅ │ next:──┼──→│ next:──┼──→│ next:──┼──→│ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head ↑slow ↑fast
4	Check fast and fast->next (fast=30, fast->next=40) - continue	Node(20)	Node(30)	Same as step 3
5	Move slow by 1 (slow=30), fast by 2 (fast=NULL)	Node(30)	NULL	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → ∅ │ next:──┼──→│ next:──┼──→│ next:──┼──→│ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head ↑slow fast=NULL
6	Check fast and fast->next (fast=NULL) - stop loop	Node(30)	NULL	Loop ends, slow points to middle node
7	Return slow->data as middle element	Node(30)	NULL	Middle element is 30

💡 fast pointer reached NULL, loop ends; 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)	NULL	NULL

Key Moments - 3 Insights

Why do we move fast pointer by two nodes but slow pointer by one?

Moving fast by two nodes and slow by one ensures that when fast reaches the end, slow is at the middle. See execution_table steps 3 and 5 where fast moves twice as fast as slow.

What happens if the list has even number of nodes?

The slow pointer will point to the second middle node when fast reaches NULL. This is shown in step 5 where slow points to Node(30) in a 4-node list.

Why does the loop stop when fast or fast->next is NULL?

Because fast moves two steps at a time, if fast or fast->next is NULL, it means we've reached the end or no further pairs exist. See step 6 where fast is NULL and loop stops.

Visual Quiz - 3 Questions

Look at the execution_table, what node does slow point to after step 3?

A Node with data 20

B Node with data 10

C Node with data 30

D NULL

💡 Hint

Check the 'slow Pointer' column in row for step 3 in execution_table

At which step does the fast pointer become NULL?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'fast Pointer' column in execution_table rows

If the list had 5 nodes instead of 4, where would slow point at loop end?

A Third node (middle)

B Second node

C Fourth node

D Fifth node

💡 Hint

The slow pointer always points to the middle node; see concept_flow and variable_tracker

Concept Snapshot

Find Middle Element of Linked List:
- Use two pointers: slow and fast starting at head
- Move slow by 1 node, fast by 2 nodes in each loop
- Loop ends when fast or fast->next is NULL
- Slow pointer then points to middle node
- Works in one pass, O(n) time, O(1) space

Full Transcript

To find the middle element of a linked list, we use two pointers called slow and fast. Both start at the head of the list. In each step, slow moves one node forward, while fast moves two nodes forward. We keep doing this until fast reaches the end of the list or there is no next node for fast. At that point, slow will be pointing to the middle node. This method works for both even and odd length lists. For even length, slow points to the second middle node. This approach is efficient because it only requires one pass through the list and uses constant extra space.