Find Middle Element of Linked List in DSA Go

Mental Model

To find the middle, use two pointers moving at different speeds so when the fast one reaches the end, the slow one is in the middle.

Analogy: Imagine walking on a path with a friend. You walk one step at a time, your friend runs two steps at a time. When your friend finishes the path, you are halfway.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Goal: Find the middle element of the linked list

Step 1: Initialize slow and fast pointers at head (node 1)

head -> [slow->1, fast->1] -> 2 -> 3 -> 4 -> 5 -> null

Why: Both pointers start at the beginning to start traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 5 -> null

Why: Slow moves one step, fast moves two steps to find middle efficiently

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->5] -> null

Why: Continue moving pointers until fast reaches end

Step 4: Fast tries to move two steps but reaches null, stop

head -> 1 -> 2 -> [slow->3] -> 4 -> 5 -> null

Why: Fast reached end, slow is at middle

Result:

head -> 1 -> 2 -> [3] -> 4 -> 5 -> null
Middle element is 3

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

func findMiddle(head *Node) *Node {
	if head == nil {
		return nil
	}

	slow := head
	fast := head

	for fast != nil && fast.next != nil {
		slow = slow.next // advance slow by one
		fast = fast.next.next // advance fast by two
	}

	return slow
}

func printList(head *Node) {
	curr := head
	for curr != nil {
		fmt.Printf("%d -> ", curr.value)
		curr = curr.next
	}
	fmt.Println("null")
}

func main() {
	// Create linked list 1->2->3->4->5->null
	n1 := &Node{value: 1}
	n2 := &Node{value: 2}
	n3 := &Node{value: 3}
	n4 := &Node{value: 4}
	n5 := &Node{value: 5}
	n1.next = n2
	n2.next = n3
	n3.next = n4
	n4.next = n5

	printList(n1)
	middle := findMiddle(n1)
	if middle != nil {
		fmt.Printf("Middle element is %d\n", middle.value)
	} else {
		fmt.Println("List is empty")
	}
}

slow := head fast := head

Initialize two pointers at the start

for fast != nil && fast.next != nil {

Loop until fast reaches end or next is nil

slow = slow.next // advance slow by one

Move slow pointer one step forward

fast = fast.next.next // advance fast by two

Move fast pointer two steps forward

return slow

Slow pointer now points to middle node

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Middle element is 3

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because we use only two pointers regardless of list size

vs Alternative: Naive approach counts nodes first then traverses again, costing O(2n); this method finds middle in one pass

Edge Cases

empty list (head is nil)

Returns nil, no middle element

DSA Go

if head == nil {
	return nil
}

list with one element

Returns the single node as middle

DSA Go

for fast != nil && fast.next != nil {

list with even number of elements

Returns the second middle node (e.g., for 4 nodes returns 3rd node)

DSA Go

for fast != nil && fast.next != nil {

When to Use This Pattern

When you need to find the middle of a linked list in one pass, use the slow and fast pointer pattern because it efficiently finds the middle without extra space.

Common Mistakes

Mistake: Moving both pointers by one step each time
Fix: Move fast pointer by two steps and slow pointer by one step to find middle correctly

Mistake: Not checking if fast or fast.next is nil before moving fast two steps
Fix: Add condition fast != nil && fast.next != nil in loop to avoid null pointer errors

Summary

Finds the middle node of a linked list using two pointers moving at different speeds.

Use when you want the middle element without counting all nodes first.

The fast pointer moves twice as fast as the slow pointer, so when fast reaches the end, slow is in the middle.

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