C++ Program to Find the Middle of a Linked List

1. Introduction

In computer science, a linked list is a sequence of data structures, which are connected together via links. Linked lists are among the simplest and most common data structures. One common problem is to find the middle element of a linked list.

In this blog post, we will learn how to write a C++ program to find the middle of the Linked List.

2. Program Overview

To find the middle of a linked list, we can use two pointers: one moving one step at a time and the other moving two steps. When the faster pointer reaches the end of the list, the slower pointer will be in the middle.

3. Code Program

#include<iostream>
using namespace std;

// Define a Node for the linked list
class Node {
public:
    int data;       // Data contained in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize node data and set next pointer to nullptr
    Node(int val): data(val), next(nullptr) {}
};

// Define a Singly Linked List
class LinkedList {
private:
    Node* head;     // Pointer to the start (head) of the list

public:
    // Constructor to initialize an empty list with head as nullptr
    LinkedList(): head(nullptr) {}

    void push(int new_data);       // Add a node to the beginning of the list
    void printMiddle();            // Print the middle element of the list
};

// Function to add a new node at the beginning of the list
void LinkedList::push(int new_data) {
    Node* new_node = new Node(new_data);   // Create a new node with given data
    new_node->next = head;                 // Make the new node point to the current head
    head = new_node;                       // Update the head to point to the new node
}

// Function to print the middle element of the linked list
void LinkedList::printMiddle() {
    Node* slow_ptr = head;          // Slow pointer: Moves one step at a time
    Node* fast_ptr = head;          // Fast pointer: Moves two steps at a time

    if (head != nullptr) {
        // Traverse the list. By the end, the slow pointer will be at the middle
        while (fast_ptr != nullptr && fast_ptr->next != nullptr) {
            fast_ptr = fast_ptr->next->next;  // Move by two nodes
            slow_ptr = slow_ptr->next;        // Move by one node
        }
        cout << "The middle element is [" << slow_ptr->data << "]" << endl;
    }
}

int main() {
    LinkedList ll;                  // Create an empty linked list

    // Push elements into the linked list and print the middle after each insertion
    for (int i = 5; i > 0; i--) {
        ll.push(i);
        ll.printMiddle();
    }

    return 0;
}

Output:

The middle element is [5]
The middle element is [4]
The middle element is [4]
The middle element is [3]
The middle element is [3]

4. Code Explanation

The LinkedList class consists of two methods:

1. push, which inserts a new element at the beginning.

2. printMiddle, which prints the middle of the linked list.

The printMiddle method uses the slow_ptr and fast_ptr technique. As the fast_ptr traverses the list two steps at a time and the slow_ptr one step at a time, by the time fast_ptr reaches the end of the list, slow_ptr will be pointing to the middle of the linked list.