C++ Linked List Exercises: Insert new node at the middle of a Singly Linked List

C++ Linked List: Exercise-7 with Solution

Write a C++ program to insert a new node at the middle of a given Singly Linked List.

Test Data:
Original list:
7 5 3 1
Singly Linked List: after insert 9 in the middle of the said list-
7 5 9 3 1
Singly Linked List: after insert 11 in the middle of the said list-
7 5 9 11 3 1
Singly Linked List: after insert 13 in the middle of the said list-
7 5 9 13 11 3 1

Sample Solution:

C++ Code:

#include <iostream> // Including input-output stream header file

using namespace std; // Using standard namespace

// Structure for defining a Node
struct Node {
    int data; // Data field to store a number
    Node *next; // Pointer to the next node
};

int sz = 0; // Initializing variable to keep track of the size of the linked list

// Function to insert a node at the beginning of the linked list
void insert(Node** head, int data) {
    Node* new_Node = new Node(); // Creating a new node
    new_Node->data = data; // Assigning data to the new node
    new_Node->next = *head; // Pointing the new node to the current head
    *head = new_Node; // Making the new node as the head
    sz++; // Increasing the size of the linked list
}

// Function to insert a node in the middle of the linked list
void insert_middle(Node** head, int data) {
    Node* new_Node = new Node(); // Creating a new node
    new_Node->data = data; // Assigning data to the new node

    if (*head == NULL) { // If the list is empty, insert at the beginning
        new_Node->data = data;
        new_Node->next = *head;
        *head = new_Node;
        sz++;
        return;
    }

    Node* temp = *head;
    // Find insertion position for middle
    int mid = (sz % 2 == 0) ? (sz / 2) : (sz + 1) / 2;
    while (--mid) {
        temp = temp->next;
    }
    new_Node->next = temp->next;
    temp->next = new_Node;
    sz++;
}

// Display all nodes in the linked list
void display_all_nodes(Node* node) {
    while (node != NULL) {
        cout << node->data << " "; // Displaying the data in the current node
        node = node->next; // Move to the next node
    }
}

int main() {
    Node* head = NULL; // Initializing the head of the linked list as NULL

    insert(&head, 1); // Inserting a node with value 1
    insert(&head, 3); // Inserting a node with value 3
    insert(&head, 5); // Inserting a node with value 5
    insert(&head, 7); // Inserting a node with value 7

    cout << "Original list:\n"; // Displaying message for the original list
    display_all_nodes(head); // Displaying all nodes in the original list

    cout << "\nSingly Linked List: after insert 9 in the middle of the said list-\n";
    insert_middle(&head, 9); // Inserting a node with value 9 in the middle of the list
    display_all_nodes(head); // Displaying all nodes in the updated list

    cout << "\nSingly Linked List: after insert 11 in the middle of the said list-\n";
    insert_middle(&head, 11); // Inserting a node with value 11 in the middle of the list
    display_all_nodes(head); // Displaying all nodes in the updated list

    cout << "\nSingly Linked List: after insert 13 in the middle of the said list-\n";
    insert_middle(&head, 13); // Inserting a node with value 13 in the middle of the list
    display_all_nodes(head); // Displaying all nodes in the updated list

    cout << endl; // Displaying newline
    return 0; // Returning from the main function
}

Sample Output:

Original list:
7 5 3 1
Singly Linked List: after insert 9 in the middle of the said list-
7 5 9 3 1
Singly Linked List: after insert 11 in the middle of the said list-
7 5 9 11 3 1
Singly Linked List: after insert 13 in the middle of the said list-
7 5 9 13 11 3 1

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Find middle element in a single linked list.
Next C++ Exercise: Get N^th node in a Singly Linked List.