Lecture 221:- Student Challenge  Finding Middle Element of a Linked List

To find the middle element of a linked list, you can use the slow and fast pointer approach. This approach uses two pointers: one that moves one step at a time (slow pointer) and another that moves two steps at a time (fast pointer). When the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

Here's the C++ implementation to find the middle element of a singly linked list:

cppCopy code

#include <iostream> class Node { public:    int data;    Node* next;    Node(int data) : data(data), next(nullptr) {} }; class LinkedList { private:    Node* head; public:    LinkedList() : head(nullptr) {}    ~LinkedList() {        Node* current = head;        while (current) {            Node* temp = current;            current = current->next;            delete temp;        }    }    void insert(int data) {        Node* newNode = new Node(data);        if (!head) {            head = newNode;        } else {            Node* current = head;            while (current->next) {                current = current->next;            }            current->next = newNode;        }    }    Node* findMiddle() {        if (!head) {            return nullptr;        }        Node* slow = head;        Node* fast = head;        while (fast && fast->next) {            slow = slow->next;            fast = fast->next->next;        }        return slow;    } }; int main() {    LinkedList list;    list.insert(1);    list.insert(2);    list.insert(3);    list.insert(4);    list.insert(5);    Node* middle = list.findMiddle();    if (middle) {        std::cout << "Middle element: " << middle->data << std::endl;    } else {        std::cout << "List is empty." << std::endl;    }    return 0; }

In this implementation, the LinkedList class is used to create a singly linked list. The insert method is used to insert elements at the end of the list. The findMiddle method uses the slow and fast pointer approach to find the middle element.

In the main function, we demonstrate how to use the LinkedList class by creating a linked list, inserting elements, and then finding the middle element using the findMiddle method. The output will be Middle element: 3, as the middle element of the list [1 -> 2 -> 3 -> 4 -> 5] is 3.