Problem Statement

Given an linked list, we aim t find the middle element. If the list contains an even number of elements, we will return the second middle element.

Examples

Example 1:

Input: Head = [1, 2, 3, 4, 5]

Output: [3, 4, 5], As we will return the middle of Linked list the further linked list will be still available.

Explanation: The middle node of the list is node 3.

Example 2:

Input: Head = [1, 2, 3, 4, 5, 6]

Output: [4, 5, 6]

Approach

To find the middle element of a linked list, we'll employ the slow and fast pointer approach. We'll use two pointers - one slow and one fast. The slow pointer traverses the list one node at a time, while the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle element (or the first middle element in the case of an even-sized list).

Algorithm:

1. Initialize two pointers, slow and fast, pointing to the head of the list.
2. Traverse the list:
   1. Move the slow pointer one step forward.
   2. Move the fast pointer two steps forward.
   3. Repeat until the fast pointer reaches the end of the list.
3. Return the data value stored in the node pointed to by the slow pointer.

Code:

#include <iostream>
using namespace std;

// Define the Node structure
class Node {
   public:
    int data;
    Node* next;

    // Constructor
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

// Function to find the middle node of the linked list
Node* findMiddleNode(Node* head) {
    Node* slow = head;
    Node* fast = head;

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

    return slow;
}

int main() {
    // Create a linked list
    Node* head = new Node(2);
    head->next = new Node(4);
    head->next->next = new Node(6);
    head->next->next->next = new Node(8);
    head->next->next->next->next = new Node(10);

    // Find the middle node of the linked list
    Node* middleNode = findMiddleNode(head);

    // Print the middle node's data
    while (middleNode != nullptr) {
        cout << middleNode->data << endl;
        middleNode = middleNode->next;
    }

    return 0;
}

// Output
6
8
10

Complexity Analysis

Time Complexity: O(n)

• Both the slow and fast pointers traverse the list once. Therefore, the time complexity of finding the middle element is linear with respect to the number of nodes in the list.

Space Complexity: O(1)

• The space complexity is constant because the operation requires only a constant amount of additional memory for the slow and fast pointers, regardless of the size of the linked list.