Middle of the Linked List - CPP Solution

1. Introduction

This blog post explores a common task in linked list manipulation: finding the middle node of a singly linked list. This problem is often encountered in various computer science applications and interviews.

Problem

Given the head of a singly linked list, the task is to return the middle node of the list. If the list has an even number of nodes, return the second middle node.

2. Solution Steps

1. Use two pointers, slow and fast.

2. slow moves one node at a time, while fast moves two nodes.

3. When fast reaches the end of the list, slow will be at the middle.

4. Return the node pointed to by slow.

3. Code Program

#include <iostream>
using namespace std;

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

// Function to find the middle of the list
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Function to print the linked list from a given node
void printFromNode(ListNode* node) {
    while (node) {
        cout << node->val << " -> ";
        node = node->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a 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 = middleNode(head);
    printFromNode(middle); // Expected output: 3 -> 4 -> 5 -> nullptr
    return 0;
}

Output:

3 -> 4 -> 5 -> nullptr

Explanation:

The middleNode function uses the two-pointer technique to find the middle of the list. 

The slow pointer moves 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 of the list. If the list has an even number of nodes, this method ensures that the slow pointer points to the second middle node, as required by the problem statement.