Insert Node at the Middle of the Linked List
“Insert Node at the Middle of the Linked List” is a basic programming problem based on linked list. Here, we are given a linked list and our task is to insert the new node at the middle of the linked list.
Examples: Current Linked List: 1 -> 2 -> 4 -> 5 -> NULL After Inserting New Node at the Middle of the Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
There are basically two methods to insert node at the middle of the linked list, which are:
- Counting based method
- Hop Jump Method
Method 1: Insert Node at the Middle of the Linked List using counting based technique
The steps required to insert node at the middle of the linked list are as follows:
- Create a new Node with desired Value in data part and NULL in pointer part.
- Check whether linked list is empty or not.
- If Linked List is empty, then new node will become head of the linked list, then return.
- If Linked is not empty, then traverse the whole linked list and count the number of nodes in the linked list.
- Again, traverse the linked list up to count/2 nodes, known as middle node.
- Now, pointer of new node will point to the next of the middle node and then pointer of middle node will point to the new node.
C++ Program to Insert node at the middle of the linked list(counting method) is as follows:
/* C++ Program to Insert Node at the Middle of the Linked List */
#include<bits/stdc++.h>
using namespace std;
/* Structure of the Node of the Linked List */
struct node
{
int data;
struct node *next;
};
/* Function to Insert Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
// Creating a new node.
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;
/* Check whether the linked list is empty or not */
/* If Linked List is empty, then new node will become head of linked list */
if(*head == NULL)
{
*head = new_node;
return;
}
/* If Linked List is not empty, then traverse the whole linked list and pointer
of last node of the linked list will point to the new node of the linked list */
struct node *temp = NULL;
temp = (*head);
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}
/* Function to Insert Node at the Middle of the Linked List */
void insert_middle(struct node **head,int ele)
{
/* Creating New Node */
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;
/* Check whether the linked list is empty or not */
/* If Linked List is empty, then new node will become head of linked list */
if(*head == NULL)
{
*head = new_node;
return;
}
/* Traverse the complete linked list and count the total number of node in it */
int count = 0;
struct node *temp = (*head);
while(temp!=NULL)
{
count++;
temp=temp->next;
}
temp = (*head);
/* Now, traverse to half of the linked linked (count/2) and insert the new node there*/
for(int i=1;i<(count/2);i++)
{
temp = temp -> next;
}
new_node->next = temp->next;
temp->next = new_node;
}
/* Function to Print the Linked List */
void print(struct node *head)
{
struct node *p = head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
int main()
{
struct node *head;
head = NULL;
/* Inserting Some Nodes in the Linked List */
insert_end(&head,1);
insert_end(&head,2);
insert_end(&head,1);
insert_end(&head,3);
cout<<"Linked list elements before inserting new node\n";
print(head);
/* Inserting New Node at the Middle of the Linked List */
insert_middle(&head,5);
cout<<"\nLinked list elements after inserting new node \n";
print(head);
}
OUTPUT: Linked list elements before inserting new node 1 2 1 3 Linked list elements after inserting new node 1 2 5 1 3
Method 2: Insert node at the middle of the linked list using hop jump technique
The steps required to insert node at the middle of the linked list are as follows:
- Initialize two pointer; slow pointer and fast pointer pointing to the head of the linked list.
- Now, traverse the whole linked list, slow pointer will increment to next node while fast pointer will increment to next to next node.
- Once, the fast pointer reaches to the end of the list, the slow pointer will point to the middle node of linked list.
- Now, the pointer of the new node will point to the next of the middle node and pointer of the middle node will point to the new node.
C++ Program to insert node at the middle of the Linked List(Hop Jump) is as follows:
/* C++ Program to Insert Node at the Middle of Linked List */
#include<bits/stdc++.h>
using namespace std;
/* Structure of the New Node */
struct node
{
int data;
struct node *next;
};
/* Function to Insert Node at the End of the Linked List */
void insert_end(struct node **head, int ele)
{
// Creating a new node.
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;
/* Check whether the linked list is empty or not */
/* If Linked List is Empty, then new node will become head of the linked list */
if(*head == NULL)
{
*head = new_node;
return;
}
/* If Linked List is not Empty, then trsaverse the completer linked list
and pointer of last node of the linked list will point to the new node */
struct node *temp = NULL;
temp = (*head);
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}
/* Function to Inset New Node at the Beginning of the Linked List */
void insert_middle(struct node **head,int ele)
{
/* Creating New Node */
struct node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;
/* If linked List is empty, then new node will become head of the Linked List */
if(*head == NULL)
{
*head = new_node;
return;
}
/* If Linked List is not empty,
Initilize two pointers; slow pointer which will traverse the list one node at a time,
and fast pointer which will traverse the list two nodes at the time. In this manner,
when fast pointer reaches the end of the linked list, the slow pointer points to the
middle of the linked list, where we need to insert new node.
*/
struct node *fast = (*head);
struct node *slow = (*head);
while(slow!=NULL && fast!=NULL && fast->next!=NULL && fast->next->next!=NULL)
{
slow = slow->next;
fast = fast->next->next;
}
new_node->next = slow -> next;
slow->next = new_node;
}
/* Function to print the complete linked list */
void print(struct node *head)
{
struct node *p = head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
int main()
{
struct node *head;
head = NULL;
/* Inserting Some Node in the Linked List */
insert_end(&head,1);
insert_end(&head,2);
insert_end(&head,1);
insert_end(&head,3);
cout<<"Linked list elements before inserting new node: \n";
print(head);
/* Inserting New Node at the middle of the Linked List */
insert_middle(&head,5);
cout<<"\nLinked list elements after inserting new node: \n";
print(head);
}
OUTPUT: Linked list elements before inserting new node: 1 2 1 3 Linked list elements after inserting new node: 1 2 5 1 3
Related Posts:
- Insert a New Node at the beginning of the Linked List.
- Insert a New Node at the end of the Linked List.
- Insert a New Node at the Sorted Linked List.
- Reverse a Linked List.
- Reverse a Linked List Using Stack.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.
- Bubble Sort on Linked List.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes of the Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.
- Delete without head pointer of the Linked List.
- Delete All Occurrences of particular node of the Linked List.
- Delete Alternate Nodes of the Linked List.
- Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
- Remove Duplicate Nodes from an Unsorted Linked List
