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: while fast != null and fast.next != null

↓

Move slow by 1 node

↓

Move fast by 2 nodes

↓

Repeat loop

↓

When loop ends, slow points to middle node

↓

Return slow.data as middle element

Two pointers move through the list at different speeds; when the fast pointer reaches the end, the slow pointer is at the middle.

Execution Sample

DSA C++

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

Node* findMiddle(Node* head) {
  Node *slow = head, *fast = head;
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

This code finds the middle node of a singly linked list using two pointers moving at different speeds.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Visual State	Note
1	Initialize slow and fast at head	Node(data:10)	Node(data:10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head	Step 1: Both pointers start at head node with value 10
2	Move slow by 1, fast by 2	Node(data:20)	Node(data:30)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head	Step 2: slow pointer at node 20, fast pointer at node 30
3	Move slow by 1, fast by 2	Node(data:30)	Node(data:50)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head	Step 3: slow pointer at node 30, fast pointer at node 50
4	Attempt to move slow by 1, fast by 2	Node(data:30)	null	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head	Step 4: fast pointer is null, slow pointer at middle node 30

💡 fast pointer reached null, loop ends; slow pointer is at middle node

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4 (End)
slow	Node(data:10)	Node(data:20)	Node(data:30)	Node(data:30)
fast	Node(data:10)	Node(data:30)	Node(data:50)	null

Key Moments - 3 Insights

Why does the fast pointer move two nodes at a time while slow moves one?

Because moving fast pointer twice as fast ensures that when fast reaches the end, slow is exactly at the middle (see execution_table steps 2 and 3).

What happens if the linked list has an even number of nodes?

The slow pointer will stop at the first of the two middle nodes because the loop ends when fast or fast.next is null (see execution_table step 4).

Why does the loop condition check both fast and fast->next?

To avoid accessing null->next which causes errors; it ensures fast can safely move two steps ahead (see execution_table step 4 where fast becomes null).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what node is the slow pointer pointing to?

A Node with data 20

B Node with data 30

C Node with data 40

D Node with data 50

💡 Hint

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

At which step does the fast pointer become null, ending the loop?

A Step 2

B Step 3

C Step 4

D It never becomes null

💡 Hint

Look at the 'fast Pointer' column in execution_table to see when it becomes null

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

A At node 4 (fourth node)

B At node 3 (third node)

C At node 5 (fifth node)

D At node 6 (last node)

💡 Hint

Recall that for even nodes, slow stops at the first middle node after loop ends (see key_moments about even nodes)

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 each step
- When fast reaches end (null), slow is at middle
- Works for odd and even length lists
- Loop condition: while(fast && fast->next)

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 this until the fast pointer reaches the end of the list. At that point, the slow pointer will be pointing to the middle node. This method works for both odd and even length lists. The loop runs while the fast pointer and its next node are not null to avoid errors. The slow pointer's position after the loop ends is the middle element of the list.

Practice

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

easy

A. Use two pointers, one moving twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle.

B. Count the total nodes first, then traverse again to the middle node.

C. Reverse the linked list and pick the first element.

D. Use a stack to store nodes and pop half of them.

Solution

1. Step 1: Understand the two-pointer technique

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

2. Step 2: Identify the middle when fast pointer reaches the end

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

3. Final Answer:

   Use two pointers, one moving twice as fast as the other; when the fast pointer reaches the end, the slow pointer is at the middle. -> Option A

4. Quick Check:

   Two-pointer approach = Fast and slow pointers [OK]

Hint: Move one pointer twice as fast; slow pointer lands in middle [OK]

Common Mistakes:

• Trying to reverse the list unnecessarily
• Counting nodes twice instead of one pass
• Using extra space like stack without need

2. Which of the following C++ code snippets correctly initializes the slow and fast pointers to find the middle of a linked list named head?

easy

A. ListNode* slow = head->next; ListNode* fast = head;

B. ListNode* slow = nullptr; ListNode* fast = head;

C. ListNode* slow = head; ListNode* fast = nullptr;

D. ListNode* slow = head; ListNode* fast = head;

Solution

1. Step 1: Initialize both pointers at the head

   Both slow and fast pointers should start at the head to traverse the list correctly.

2. Step 2: Avoid null initialization for slow or fast

   Initializing slow or fast to nullptr will cause errors or skip nodes.

3. Final Answer:

   ListNode* slow = head; ListNode* fast = head; -> Option D

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head node [OK]

Common Mistakes:

• Initializing pointers to nullptr causing runtime errors
• Starting slow pointer at head->next skipping first node
• Starting fast pointer at nullptr causing immediate stop

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

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

Node* findMiddle(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

int main() {
  Node n1 = {1, nullptr};
  Node n2 = {2, nullptr};
  Node n3 = {3, nullptr};
  Node n4 = {4, nullptr};
  Node n5 = {5, nullptr};
  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n4;
  n4.next = &n5;
  Node* mid = findMiddle(&n1);
  std::cout << mid->data << std::endl;
  return 0;
}

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Trace slow and fast pointers through the list

   Initially, slow=1, fast=1; after first loop, slow=2, fast=3; second loop, slow=3, fast=5; next loop fast->next is nullptr, stop.

2. Step 2: Identify slow pointer position at loop end

   Slow pointer is at node with data 3, which is the middle element.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Middle element = 3 [OK]

Hint: Fast moves two steps, slow moves one; slow ends at middle [OK]

Common Mistakes:

• Assuming middle is 2 or 4 instead of 3
• Not checking fast->next before moving fast
• Confusing zero-based indexing with node values

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

Node* findMiddle(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

medium

A. Return fast pointer instead of slow.

B. The while condition should check both fast and fast->next to avoid null pointer dereference.

C. Move slow pointer two steps instead of one.

D. Initialize slow to nullptr instead of head.

Solution

1. Step 1: Analyze the while loop condition

   The loop only checks if fast != nullptr, but fast->next might be nullptr causing a crash when accessing fast->next->next.

2. Step 2: Correct the condition to check fast->next as well

   Change the loop condition to while (fast != nullptr && fast->next != nullptr) to safely move fast pointer two steps.

3. Final Answer:

   The while condition should check both fast and fast->next to avoid null pointer dereference. -> Option B

4. Quick Check:

   Check fast and fast->next before moving fast [OK]

Hint: Always check fast and fast->next in loop condition [OK]

Common Mistakes:

• Not checking fast->next causing runtime errors
• Moving slow pointer two steps incorrectly
• Returning wrong pointer at the end

5. Given a singly linked list with an even number of nodes, how can you modify the two-pointer approach to return the first middle element instead of the second middle element?

hard

A. Initialize slow pointer to head->next instead of head.

B. Move fast pointer one step at a time instead of two.

C. Initialize fast pointer to head->next instead of head.

D. Use a stack to store nodes and pop half.

Solution

1. Step 1: Understand default behavior for even length lists

   Normally, with both pointers starting at head, slow ends at the second middle node for even length lists.

2. Step 2: Modify fast pointer start to head->next

   Starting fast at head->next causes slow to stop at the first middle node when fast reaches the end.

3. Final Answer:

   Initialize fast pointer to head->next instead of head. -> Option C

4. Quick Check:

   Fast starts at head->next for first middle [OK]

Hint: Start fast at second node to get first middle in even list [OK]

Common Mistakes:

• Changing slow pointer start instead of fast
• Moving fast pointer one step breaks logic
• Using extra space unnecessarily