Find Middle Element of Linked List in DSA Javascript - 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

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

Execution Sample

DSA Javascript

function findMiddle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.data;
}

Finds the middle element by moving slow pointer one step and fast pointer two steps until fast reaches the end.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Linked List State	Visual State
1	Initialize slow and fast at head	10	10	10 -> 20 -> 30 -> 40 -> 50 -> null	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ → │ data:20│ → │ data:30│ → │ data:40│ → │ data:50│ → null │ next:──┼→ │ next:──┼→ │ next:──┼→ │ next:──┼→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head = slow = fast
2	Check fast and fast.next (fast=10, fast.next=20)	10	10	Condition true, continue loop	Pointers at start
3	Move slow to next (20), fast to next.next (30)	20	30	10 -> 20 -> 30 -> 40 -> 50 -> null	slow → 20, fast → 30
4	Check fast and fast.next (fast=30, fast.next=40)	20	30	Condition true, continue loop	Pointers moved
5	Move slow to next (30), fast to next.next (50)	30	50	10 -> 20 -> 30 -> 40 -> 50 -> null	slow → 30, fast → 50
6	Check fast and fast.next (fast=50, fast.next=null)	30	50	Condition false, exit loop	fast.next is null, stop
7	Return slow.data	30	50	Middle element found	Middle element is 30

💡 fast.next is null at step 6, loop ends; slow points to middle node

Variable Tracker

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

Key Moments - 3 Insights

Why does the loop stop when fast.next is null, not when fast is null?

Because fast moves two steps at a time, checking fast.next ensures we don't access null.next causing error. See step 6 in execution_table where fast=50 and fast.next=null stops the loop safely.

Why does slow pointer point to the middle when fast reaches the end?

Slow moves one step each loop while fast moves two. When fast reaches the end, slow has moved half the distance, landing on the middle node. Refer to steps 3, 5, and 7 in execution_table.

What if the list has even number of nodes? Which node is middle?

In even length lists, slow will point to the second middle node because fast will become null after passing the last node. This code returns the second middle node. This is shown by the loop condition in step 2 and 6.

Visual Quiz - 3 Questions

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

A Node with data 30

B Node with data 40

C Node with data 20

D Node with data 50

💡 Hint

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

At which step does the loop condition become false?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Operation' and 'Linked List State' columns in execution_table to find when fast.next is null

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

A 3rd node

B 5th node

C 4th node

D 6th node

💡 Hint

Recall that slow points to the second middle node in even length lists as explained in key_moments

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 loop
- Loop ends when fast or fast.next is null
- slow points to middle node at loop end
- Returns middle node's data
- Works for odd and even length lists (second middle for even)

Full Transcript

This visualization shows how to find the middle element of a linked list using two pointers. Both pointers start at the head node. In each step, the slow pointer moves one node forward, while the fast pointer moves two nodes forward. The loop continues as long as fast and fast.next are not null. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. The execution table tracks the positions of slow and fast pointers at each step, showing the linked list state and visual pointer positions. Key moments clarify why the loop condition checks fast.next and how the slow pointer ends up at the middle. The quiz questions test understanding of pointer positions and loop termination. This method efficiently finds the middle element in a single pass.

Practice

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

easy

A. Reverse the list and pick the last element

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

C. Count all nodes first, then traverse again to the middle node

D. Use two pointers moving at the same speed and pick the first pointer's position

Solution

1. Step 1: Understand two-pointer technique

   One pointer (fast) moves two nodes at a time, the other (slow) moves one node at a time.

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

   When fast pointer reaches the end of the list, slow pointer will be at the middle node.

3. Final Answer:

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

4. Quick Check:

   Two-pointer technique = fast & slow pointers [OK]

Hint: Fast pointer moves 2x speed, slow pointer at middle when fast ends [OK]

Common Mistakes:

• Trying to reverse the list unnecessarily
• Counting nodes twice instead of using two pointers
• Moving both pointers at the same speed

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

easy

A. let slow = head.next; let fast = head;

B. let slow = null; let fast = head.next;

C. let slow = head; let fast = head;

D. let slow = head; let fast = null;

Solution

1. Step 1: Initialize both pointers at head

   Both slow and fast pointers start at the head node to begin traversal.

2. Step 2: Confirm correct initialization

   Starting both at head allows fast to move ahead and slow to lag behind properly.

3. Final Answer:

   let slow = head; let fast = head; -> Option C

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both slow and fast pointers at head node [OK]

Common Mistakes:

• Starting slow or fast at null or head.next incorrectly
• Swapping slow and fast initialization
• Starting fast pointer at null causing errors

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

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);

function findMiddle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.value;
}

console.log(findMiddle(head));

medium

A. 20

B. 50

C. 40

D. 30

Solution

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

   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 at loop end

   Slow pointer is at node with value 30, which is the middle element.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Middle element = 30 [OK]

Hint: Fast moves 2 steps, slow moves 1; slow ends at middle [OK]

Common Mistakes:

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

4. The following code is intended to find the middle element of a linked list, but it has a bug. What is the bug?

function findMiddle(head) {
  let slow = head;
  let fast = head.next;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.value;
}

medium

A. Fast pointer should start at head, not head.next

B. Slow pointer should start at head.next, not head

C. Loop condition should be while (fast !== null)

D. Return statement should return fast.value

Solution

1. Step 1: Analyze pointer initialization

   Fast pointer starts at head.next, which causes slow pointer to point to the first middle in even-length lists incorrectly.

2. Step 2: Correct initialization for accurate middle

   Fast pointer should start at head to ensure slow pointer reaches the true middle node.

3. Final Answer:

   Fast pointer should start at head, not head.next -> Option A

4. Quick Check:

   Fast pointer must start at head [OK]

Hint: Start fast pointer at head to avoid off-by-one errors [OK]

Common Mistakes:

• Starting fast pointer at head.next causing wrong middle
• Changing loop condition incorrectly
• Returning fast pointer value instead of slow

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 fast pointer at head.next and slow pointer at head

B. Initialize slow pointer at head.next and fast pointer at head

C. Move slow pointer twice and fast pointer once in the loop

D. Return fast pointer's value instead of slow pointer's value

Solution

1. Step 1: Understand default behavior

   Normally, both pointers start at head, so slow points to second middle in even-length lists.

2. Step 2: Modify initialization to get first middle

   Starting fast pointer at head.next causes slow pointer to move fewer steps, landing on the first middle node.

3. Final Answer:

   Initialize fast pointer at head.next and slow pointer at head -> Option A

4. Quick Check:

   Fast starts at head.next for first middle [OK]

Hint: Start fast at head.next to get first middle in even lists [OK]

Common Mistakes:

• Swapping slow and fast initialization incorrectly
• Changing pointer movement speeds
• Returning fast pointer value without logic