Find the Middle of a Linked List (Slow & Fast Pointer Technique) in DSA

Introduction

The Find the Middle of a Linked List problem is a very common DSA interview question related to linked lists. Interviewers like this problem because it checks your understanding of pointer movement, traversal logic, and optimization.

In simple words, this problem asks you to find the middle node of a linked list in one traversal.

What Does “Middle of a Linked List” Mean?

Given a linked list:

If the list has odd number of nodes, there is exactly one middle node
If the list has even number of nodes, most interviewers ask you to return the second middle node

Example

Odd length list:

1 → 2 → 3 → 4 → 5

Middle node = 3

Even length list:

1 → 2 → 3 → 4 → 5 → 6

Middle node = 4 (second middle)

Why Brute Force Approach is Not Ideal

A simple approach is:

Count the total number of nodes
Traverse again to reach the middle

Problems with This Approach

Requires two traversals
Less efficient

Interviewers usually expect a single-pass solution.

Optimized Approach: Slow and Fast Pointer Technique

The most efficient way to solve this problem is by using two pointers.

Key Idea (Very Simple)

Slow pointer moves one step at a time
Fast pointer moves two steps at a time

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

Why This Technique Works

Because the fast pointer moves twice as fast:

When fast reaches the end of the list
Slow has covered half the distance

So slow naturally lands on the middle node.

Step-by-Step Explanation

Steps:

Initialize both slow and fast pointers at the head
Move slow by one step
Move fast by two steps
Repeat until fast reaches the end or becomes null
slow now points to the middle node

Dry Run Example (Odd Length)

Linked List:

1 → 2 → 3 → 4 → 5

Step	Slow	Fast
Start	1	1
1	2	3
2	3	5

Fast reaches end → Slow is at 3 (middle)

Dry Run Example (Even Length)

Linked List:

1 → 2 → 3 → 4 → 5 → 6

Step	Slow	Fast
Start	1	1
1	2	3
2	3	5
3	4	null

Slow is at 4 (second middle)

Code Implementation

C++ Code

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Java Code

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Python Code

def middleNode(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(1)

This makes the solution optimal.

Important Edge Cases

Empty linked list
Single node linked list
Two-node linked list

Always discuss these cases in interviews.

Common Interview Follow-Up Questions

Return first middle instead of second
Find middle in circular linked list
Use slow-fast pointer in other problems

This technique is reused in many linked list problems.

Summary

The Find the Middle of a Linked List problem is a classic example of how the Slow and Fast Pointer technique simplifies linked list traversal. By moving two pointers at different speeds, you can find the middle element in a single pass without extra space. Mastering this technique is essential for solving many linked list problems and performing well in coding interviews.