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

Concept Flow - Find Middle Element of Linked List

Start: head points to first node

↓

Initialize two pointers: slow and fast at head

↓

Move fast by 2 nodes, slow by 1 node

↓

Check if fast or fast.next is null?

Yes→Stop: slow is at middle

No↓

Repeat moving pointers

↓

Return slow.data as middle element

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

Execution Sample

DSA Go

func findMiddle(head *Node) *Node {
    slow, fast := head, head
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

This code finds the middle node of a linked list by moving fast pointer twice as fast as slow pointer.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Visual State
1	Initialize slow and fast at head	Node(10)	Node(10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head=slow=fast
2	Move slow by 1, fast by 2	Node(20)	Node(30)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
3	Move slow by 1, fast by 2	Node(30)	Node(50)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│──→ │ data:50│ │ next:──┼ │ next:──┼ │ next:──┼ │ next:──┼ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head slow fast
4	Check fast.next == nil (fast at Node(50))	Node(30)	Node(50)	Stop: fast.next is nil, slow is at middle

💡 fast reached end of list (fast.next is nil), slow pointer is at middle node

Variable Tracker

Variable	Start	After Step 2	After Step 3	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 by two nodes and slow pointer by one?

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

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

The slow pointer stops at the second middle node in even length lists because fast pointer becomes nil after moving two steps (see exit at step 4).

Why do we check both fast != nil and fast.next != nil in the loop?

To avoid accessing next of a nil pointer which causes error. This check ensures safe traversal (see condition before step 3).

Visual Quiz - 3 Questions

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

A Node with data 20

B Node with data 40

C Node with data 30

D Node with data 50

💡 Hint

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

At which step does the loop stop because fast.next is nil?

A Step 3

B Step 4

C Step 2

D Step 1

💡 Hint

Look at the 'Operation' and 'exit_note' in execution_table for stopping condition

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

A At node 4 (fourth node)

B At node 5 (fifth node)

C At node 3 (third node)

D At node 6 (last node)

💡 Hint

Think about how slow moves one step and fast moves two steps; slow stops when fast or fast.next is nil

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 (nil) or fast.next is nil, slow is at middle
- Works in one pass, O(n) time, O(1) space
- Handles odd and even length lists gracefully

Full Transcript

To find the middle element of a linked list, we use two pointers called slow and fast. Both start at the head node. 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 fast.next is nil. At that point, slow points to the middle node. This method finds the middle in one pass efficiently. For example, in a list with nodes 10->20->30->40->50, slow ends at node 30 when fast reaches node 50. This approach works for both odd and even length lists and avoids errors by checking fast and fast.next before moving fast pointer.

Practice

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

easy

A. Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end

B. Count all nodes first, then access the middle by index

C. Use two pointers both moving one step at a time

D. Reverse the list and pick the first element

Solution

1. Step 1: Understand two-pointer technique

   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 reaches end

   When the fast pointer reaches the end of the list, 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 A

4. Quick Check:

   Two-pointer technique = Use one slow pointer moving one step and one fast pointer moving two steps until fast reaches the end [OK]

Hint: Move fast pointer twice as fast as slow pointer [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 Go code snippets correctly initializes two pointers to find the middle of a linked list named head?

easy

A. slow, fast := nil, head

B. slow := head; fast := nil

C. slow, fast := head, head

D. slow, fast := head.next, head.next.next

Solution

1. Step 1: Initialize both pointers at head

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

2. Step 2: Check pointer initialization correctness

   slow, fast := head, head correctly sets slow and fast to head, allowing traversal from the start.

3. Final Answer:

   slow, fast := head, head -> Option C

4. Quick Check:

   Both pointers start at head = slow, fast := head, head [OK]

Hint: Start both pointers at head node [OK]

Common Mistakes:

• Setting fast pointer to nil initially
• Starting pointers at different nodes
• Skipping nodes at initialization

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

type Node struct {
    val  int
    next *Node
}

func findMiddle(head *Node) int {
    slow, fast := head, head
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
    }
    return slow.val
}

// List: 10 -> 20 -> 30 -> 40 -> 50 -> nil
head := &Node{10, &Node{20, &Node{30, &Node{40, &Node{50, nil}}}}}
fmt.Println(findMiddle(head))

medium

A. 30

B. 20

C. 40

D. 50

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 nil.

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 A

4. Quick Check:

   Middle element = 30 [OK]

Hint: Trace slow pointer moves until fast reaches end [OK]

Common Mistakes:

• Returning fast pointer value instead of slow
• Stopping loop too early
• Confusing node values

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

func findMiddle(head *Node) int {
    slow, fast := head, head
    for fast.next != nil && fast.next.next != nil {
        slow = slow.next
        fast = fast.next.next
    }
    return slow.val
}

medium

A. The slow pointer should move two steps instead of one

B. The pointers should be initialized to nil

C. The function should return fast.val instead of slow.val

D. The loop condition should check fast != nil before fast.next

Solution

1. Step 1: Analyze loop condition safety

   The loop checks fast.next and fast.next.next but does not check if fast itself is nil, risking a runtime error if fast is nil.

2. Step 2: Correct loop condition to avoid nil pointer dereference

   The condition should first check fast != nil, then fast.next != nil to safely access fast.next.next.

3. Final Answer:

   The loop condition should check fast != nil before fast.next -> Option D

4. Quick Check:

   Check fast != nil first to avoid errors [OK]

Hint: Always check pointer != nil before accessing next [OK]

Common Mistakes:

• Ignoring nil checks causing runtime panic
• Moving slow pointer incorrectly
• Returning wrong pointer value

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

hard

A. Reverse the list and pick the middle element

B. Initialize fast pointer to head.next instead of head

C. Return fast pointer value instead of slow pointer value

D. Move slow pointer two steps and fast pointer one step

Solution

1. Step 1: Understand middle element in even-length list

   For even nodes, two middle elements exist; the second middle is the one after the first middle.

2. Step 2: Modify fast pointer start to shift middle selection

   Starting fast pointer at head.next causes slow pointer to move to the second middle when fast reaches the end.

3. Final Answer:

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

4. Quick Check:

   Start fast at head.next for second middle [OK]

Hint: Start fast pointer one step ahead for second middle [OK]

Common Mistakes:

• Moving pointers incorrectly
• Returning fast pointer value
• Reversing list unnecessarily