How to Find Middle of Linked List in C++ Quickly

To find the middle of a linked list in C++, use two pointers: slow moves one step at a time, and fast moves two steps. When fast reaches the end, slow will be at the middle node.

Syntax

The common pattern uses two pointers to traverse the linked list:

• slow: moves one node at a time
• fast: moves two nodes at a time

When fast reaches the end (null), slow points to the middle node.

cpp

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

Example

This example creates a linked list with 5 nodes and finds the middle node using the fast and slow pointer method.

cpp

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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

int main() {
    // Create linked list: 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    ListNode* middle = findMiddle(head);
    std::cout << "Middle node value: " << middle->val << std::endl;

    // Clean up memory
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* next = current->next;
        delete current;
        current = next;
    }
    return 0;
}

Output

Middle node value: 3

Common Pitfalls

Common mistakes include:

• Not checking if the list is empty (head == nullptr).
• Advancing fast without checking if fast->next is null, causing runtime errors.
• Confusing the middle node when the list has even length (this method returns the second middle node).

cpp

/* Wrong way: missing fast->next check causes crash */
ListNode* findMiddleWrong(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr) { // Missing fast->next check
        slow = slow->next;
        fast = fast->next->next; // May cause nullptr dereference
    }
    return slow;
}

/* Right way: check both fast and fast->next */
ListNode* findMiddleRight(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Quick Reference

Tips to find middle of linked list:

• Use two pointers: slow and fast.
• Move slow by one step, fast by two steps.
• Stop when fast reaches end or null.
• slow points to middle node.
• For even length, this returns the second middle node.

Key Takeaways

Use two pointers moving at different speeds to find the middle efficiently.

Always check for null pointers to avoid runtime errors.

This method returns the second middle node if the list length is even.

Free allocated memory after use to prevent leaks.

The approach works in a single pass with O(n) time and O(1) space.