Middle Element of the Linked List

[Naive Approach] By Counting Nodes – O(n) Time and O(1) Space

Approach

1. Traverse the linked list and count the number of nodes (n).
    
2. Traverse the list again, stopping at n/2 to get the middle node.

Implementation

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = nullptr;
    }
};

void findMiddle(Node* head) {
    int count = 0;
    Node* temp = head;
    
    while (temp != nullptr) { // First traversal to count nodes
        count++;
        temp = temp->next;
    }
    
    temp = head;
    for (int i = 0; i < count / 2; i++) { // Second traversal to middle node
        temp = temp->next;
    }
    cout << "Middle element: " << temp->data << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    
    findMiddle(head);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Middle element: 3

Complexity Analysis

• Time Complexity: O(n), as we traverse the list twice.
   
• Space Complexity: O(1), since no extra space is used.

[Expected Approach] By Tortoise and Hare Algorithm – O(n) Time and O(1) Space

Approach

1. Use two-pointer: slow and fast.
    
2. slow moves one step at a time, while fast moves two steps.
    
3. When fast reaches the end, slow will be at the middle.

Implementation

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = nullptr;
    }
};

void findMiddle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    cout << "Middle element: " << slow->data << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    
    findMiddle(head);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Middle element: 3

Complexity Analysis

• Time Complexity: O(n), as we traverse the list only once.
   
• Space Complexity: O(1), since we use only two pointers.

Frequently Asked Questions

What happens if the linked list is empty?

If the linked list is empty, both methods will fail. A check for an empty list should be added before traversal.

What if the linked list has an even number of nodes?

The middle node can be the first of the two middle nodes, or we can print both, depending on the implementation.

Which approach is better for large linked lists?

The Tortoise and Hare algorithm is more efficient as it only requires one traversal, making it faster than the naive approach.

Conclusion

In this article, we discussed how to find the middle element of a linked list using efficient methods. The most common approach is the two-pointer technique, where one pointer moves twice as fast as the other, ensuring the middle is reached in a single traversal. Understanding this method helps in optimizing linked list operations and improving coding efficiency in interviews and real-world applications.