Middle Of Linked List

#include <bits/stdc++.h>             // Includes all standard C++ libraries
using namespace std;

class Node {
public:
    int data;                        // Value in the node
    Node* next;                      // Pointer to the next node

    Node(int data) {                 // Constructor to initialize a new node
        this->data = data;
        this->next = NULL;
    }
};


void printList(Node* head) {
    if(head == NULL) {
        cout << "List is Empty!" << endl;
        return;
    }

    cout << "Singly List : ";
    while(head != NULL) {
        cout << head->data << " ";   // Print node value
        head = head->next;           // Move to next node
    }
    cout << endl;
}


void insertAtHead(Node* &head, int data) {
    Node *temp = new Node(data);     // Create new node
    temp->next = head;               // Point it to current head
    head = temp;                     // Update head
}

void insertAtTail(Node* &tail, int data) {
    Node *temp = new Node(data);     // Create new node
    tail->next = temp;               // Append after current tail
    tail = temp;                     // Update tail
}


void insertAtMiddle(Node* &head, Node* &tail, int data, int pos) {
    if(pos == 1) {
        insertAtHead(head, data);    // Special case: insert at head
        return;
    }

    Node *temp = head;
    while(temp != NULL && pos > 2) { // Move to (pos-1)th node
        temp = temp->next;
        pos--;
    }

    if(temp == NULL || pos <= 0) {
        cout << "Invalid Position!" << endl;
        return;
    }

    Node *insertNode = new Node(data);
    insertNode->next = temp->next;   // Link new node to next node
    temp->next = insertNode;         // Link previous node to new node

    if(insertNode->next == NULL) {   // If inserted at end, update tail
        tail = insertNode;
    }
}


void deletePosition(Node* &head, int pos) {
    Node *temp = head;

    if(pos == 1) {                   // Special case: delete head
        head = head->next;
        delete temp;
        return;
    }

    while(temp != NULL && pos > 2) { // Move to (pos-1)th node
        temp = temp->next;
        pos--;
    }

    if(temp == NULL || temp->next == NULL || pos <= 0) {
        cout << "Invalid Position!" << endl;
        return;
    }

    Node* target = temp->next;       // Node to delete
    temp->next = target->next;       // Skip the target node
    delete target;
}


void deleteValue(Node* &head, int val) {
    Node* temp = head->next;
    Node* prev = head;

    if(head->data == val) {          // If head contains the value
        head = head->next;
        delete prev;
        return;
    }

    while(temp != NULL) {
        if(temp->data == val) {
            val = INT_MIN;           // Mark as found
            break;
        }
        prev = temp;
        temp = temp->next;
    }

    if(prev->next == NULL || val != INT_MIN) {
        cout << "Value Not Found!" << endl;
        return;
    }

    prev->next = temp->next;         // Remove node
    delete temp;
}


Node* getMiddle(Node* head) {
    if(head == NULL || head->next == NULL) {
        return head;                 // 0 or 1 node only
    }

    Node* fast = head;              // Fast pointer moves 2 steps
    Node* slow = head;              // Slow pointer moves 1 step

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

    return slow;                    // When fast reaches end, slow is at middle
}


int main() {
    Node *head = new Node(1);        // Create first node
    Node *tail = head;

    for(int i=1; i<=5; i++) {
        insertAtTail(tail, pow(2,i)); // Insert 2, 4, 8, 16, 32
    }

    printList(head);                 // Print the entire list

    Node* mid = getMiddle(head);     // Get middle node
    cout << "Middle Node : " << mid->data << endl;

    return 0;
}

Initial List:

head → 1 → 2 → 4 → 8 → 16 → 32 → NULL

Middle Node (getMiddle):

• slow and fast pointers start at 1.
• Step 1: slow = 2, fast = 4
• Step 2: slow = 4, fast = 16
• Step 3: slow = 8, fast = NULL (end reached)
• So the middle node is 8

Final Output:

Singly List : 1 2 4 8 16 32
Middle Node : 8