Given a linked list containing n nodes. The problem is to insert a new node with data x in the middle of the list. If n is even, then insert the new node after the (n/2)th node, else insert the new node after the (n+1)/2th node.
Examples:
Input : list: 1->2->4->5, x = 3
Output : 1->2->3->4->5Input : list: 5->10->4->32->16, x = 41
Output : 5->10->4->41->32->16
Insert node into the middle of the linked list using the length of the Linked List:
The idea is to first find the length of linked list and then insert the x node after the half length of the linked list.
Follow the steps below to solve the problem:
- Iterate over the linked list to calculate the length
- Now insert the node x in the middle of the linked list i.e (n + 1) / 2
C++
// C++ implementation to insert node at the middle // of the linked list #include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; Node* next; }; // function to create and return a node Node* getNode(int data) { // allocating space Node* newNode = (Node*)malloc(sizeof(Node)); // inserting the required data newNode->data = data; newNode->next = NULL; return newNode; } // function to insert node at the middle // of the linked list void insertAtMid(Node** head_ref, int x) { // if list is empty if (*head_ref == NULL) *head_ref = getNode(x); else { // get a new node Node* newNode = getNode(x); Node* ptr = *head_ref; int len = 0; // calculate length of the linked list //, i.e, the number of nodes while (ptr != NULL) { len++; ptr = ptr->next; } // 'count' the number of nodes after which // the new node is to be inserted int count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = *head_ref; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr->next; // insert the 'newNode' and adjust the // required links newNode->next = ptr->next; ptr->next = newNode; } } // function to display the linked list void display(Node* head) { while (head != NULL) { cout << head->data << " "; head = head->next; } } // Driver program to test above int main() { // Creating the list 1->2->4->5 Node* head = NULL; head = getNode(1); head->next = getNode(2); head->next->next = getNode(4); head->next->next->next = getNode(5); cout << "Linked list before insertion: "; display(head); int x = 3; insertAtMid(&head, x); cout << "\nLinked list after insertion: "; display(head); return 0; } |
Java
// Java implementation to insert node // at the middle of the linked list import java.util.*; import java.lang.*; import java.io.*; class LinkedList { static Node head; // head of list /* Node Class */ static class Node { int data; Node next; // Constructor to create a new node Node(int d) { data = d; next = null; } } // function to insert node at the // middle of the linked list static void insertAtMid(int x) { // if list is empty if (head == null) head = new Node(x); else { // get a new node Node newNode = new Node(x); Node ptr = head; int len = 0; // calculate length of the linked list //, i.e, the number of nodes while (ptr != null) { len++; ptr = ptr.next; } // 'count' the number of nodes after which // the new node is to be inserted int count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = head; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr.next; // insert the 'newNode' and adjust // the required links newNode.next = ptr.next; ptr.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } // Driver program to test above public static void main (String[] args) { // Creating the list 1.2.4.5 head = null; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); System.out.println("Linked list before "+ "insertion: "); display(); int x = 3; insertAtMid(x); System.out.println("\nLinked list after"+ " insertion: "); display(); } } // This article is contributed by Chhavi |
Python3
# Python3 implementation to insert node # at the middle of a linked list # Node class class Node: # constructor to create a new node def __init__(self, data): self.data = data self.next = None # function to insert node at the # middle of linked list given the head def insertAtMid(head, x): if(head == None): #if the list is empty head = Node(x) else: # create a new node for the value # to be inserted newNode = Node(x) ptr = head length = 0 # calculate the length of the linked # list while(ptr != None): ptr = ptr.next length += 1 # 'count' the number of node after which # the new node has to be inserted if(length % 2 == 0): count = length / 2 else: (length + 1) / 2 ptr = head # move ptr to the node after which # the new node has to inserted while(count > 1): count -= 1 ptr = ptr.next # insert the 'newNode' and adjust # links accordingly newNode.next = ptr.next ptr.next = newNode # function to display the linked list def display(head): temp = head while(temp != None): print(str(temp.data), end = " ") temp = temp.next # Driver Code # Creating the linked list 1.2.4.5 head = Node(1) head.next = Node(2) head.next.next = Node(4) head.next.next.next = Node(5) print("Linked list before insertion: ", end = "") display(head) # inserting 3 in the middle of the linked list. x = 3insertAtMid(head, x) print("\nLinked list after insertion: " , end = "") display(head) # This code is contributed by Pranav Devarakonda |
C#
// C# implementation to insert node // at the middle of the linked list using System; public class LinkedList { static Node head; // head of list /* Node Class */ public class Node { public int data; public Node next; // Constructor to create a new node public Node(int d) { data = d; next = null; } } // function to insert node at the // middle of the linked list static void insertAtMid(int x) { // if list is empty if (head == null) head = new Node(x); else { // get a new node Node newNode = new Node(x); Node ptr = head; int len = 0; // calculate length of the linked list //, i.e, the number of nodes while (ptr != null) { len++; ptr = ptr.next; } // 'count' the number of nodes after which // the new node is to be inserted int count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = head; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr.next; // insert the 'newNode' and adjust // the required links newNode.next = ptr.next; ptr.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } } // Driver code public static void Main () { // Creating the list 1.2.4.5 head = null; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); Console.WriteLine("Linked list before "+ "insertion: "); display(); int x = 3; insertAtMid(x); Console.WriteLine("\nLinked list after"+ " insertion: "); display(); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation to insert node // at the middle of the linked list var head; // head of list /* Node Class */ class Node { // Constructor to create a new node constructor(d) { this.data = d; this.next = null; } } // function to insert node at the // middle of the linked list function insertAtMid(x) { // if list is empty if (head == null) head = new Node(x); else { // get a new node var newNode = new Node(x); var ptr = head; var len = 0; // calculate length of the linked list // , i.e, the number of nodes while (ptr != null) { len++; ptr = ptr.next; } // 'count' the number of nodes after which // the new node is to be inserted var count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = head; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr.next; // insert the 'newNode' and adjust // the required links newNode.next = ptr.next; ptr.next = newNode; } } // function to display the linked list function display() { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } } // Driver program to test above // Creating the list 1.2.4.5 head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); document.write("Linked list before " + "insertion: "); display(); var x = 3; insertAtMid(x); document.write("<br/>Linked list after" + " insertion: "); display(); // This code contributed by Rajput-Ji </script> |
Output
Linked list before insertion: 1 2 4 5 Linked list after insertion: 1 2 3 4 5
Time Complexity: O(N), Using a loop to traverse n times. Where n is the number of nodes in the linked list.
Auxiliary Space: O(1)
Insert node into the middle of the linked list using Two Pointers:
Based on the tortoise and hare algorithm which uses two pointers, one known as slow and the other known as fast.
Follow the steps below to solve the problem:
- Initialize two-pointers fast and slow with head
- Move fast by two steps i.e fast = fast->next->next till it reaches end
- And slow = slow->next
- Now append node x after slow i.e. slow->next = x
Below is the implementation of the above approach:
C++
// C++ implementation to insert node at the middle // of the linked list #include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; Node* next; }; // function to create and return a node Node* getNode(int data) { // allocating space Node* newNode = (Node*)malloc(sizeof(Node)); // inserting the required data newNode->data = data; newNode->next = NULL; return newNode; } // function to insert node at the middle // of the linked list void insertAtMid(Node** head_ref, int x) { // if list is empty if (*head_ref == NULL) *head_ref = getNode(x); else { // get a new node Node* newNode = getNode(x); // assign values to the slow and fast // pointers Node* slow = *head_ref; Node* fast = (*head_ref)->next; while (fast && fast->next) { // move slow pointer to next node slow = slow->next; // move fast pointer two nodes at a time fast = fast->next->next; } // insert the 'newNode' and adjust the // required links newNode->next = slow->next; slow->next = newNode; } } // function to display the linked list void display(Node* head) { while (head != NULL) { cout << head->data << " "; head = head->next; } } // Driver program to test above int main() { // Creating the list 1->2->4->5 Node* head = NULL; head = getNode(1); head->next = getNode(2); head->next->next = getNode(4); head->next->next->next = getNode(5); cout << "Linked list before insertion: "; display(head); int x = 3; insertAtMid(&head, x); cout << "\nLinked list after insertion: "; display(head); return 0; } |
Java
// Java implementation to insert node // at the middle of the linked list import java.util.*; import java.lang.*; import java.io.*; class LinkedList { static Node head; // head of list /* Node Class */ static class Node { int data; Node next; // Constructor to create a new node Node(int d) { data = d; next = null; } } // function to insert node at the // middle of the linked list static void insertAtMid(int x) { // if list is empty if (head == null) head = new Node(x); else { // get a new node Node newNode = new Node(x); // assign values to the slow // and fast pointers Node slow = head; Node fast = head.next; while (fast != null && fast.next != null) { // move slow pointer to next node slow = slow.next; // move fast pointer two nodes // at a time fast = fast.next.next; } // insert the 'newNode' and adjust // the required links newNode.next = slow.next; slow.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } // Driver program to test above public static void main (String[] args) { // Creating the list 1.2.4.5 head = null; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); System.out.println("Linked list before"+ " insertion: "); display(); int x = 3; insertAtMid(x); System.out.println("\nLinked list after"+ " insertion: "); display(); } } // This article is contributed by Chhavi |
Python3
# Python implementation to insert node # at the middle of the linked list # Node Class class Node : def __init__(self, d): self.data = d self.next = None class LinkedList: # function to insert node at the # middle of the linked list def __init__(self): self.head = None # Function to insert a new node # at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def insertAtMid(self, x): # if list is empty if (self.head == None): self.head = Node(x) else: # get a new node newNode = Node(x) # assign values to the slow # and fast pointers slow = self.head fast = self.head.next while (fast != None and fast.next != None): # move slow pointer to next node slow = slow.next # move fast pointer two nodes # at a time fast = fast.next.next # insert the 'newNode' and # adjust the required links newNode.next = slow.next slow.next = newNode # function to display the linked list def display(self): temp = self.head while (temp != None): print(temp.data, end = " "), temp = temp.next # Driver Code # Creating the list 1.2.4.5 ll = LinkedList() ll.push(5) ll.push(4) ll.push(2) ll.push(1) print("Linked list before insertion: "), ll.display() x = 3ll.insertAtMid(x) print("\nLinked list after insertion: "), ll.display() # This code is contributed by prerna saini |
C#
// C# implementation to insert node // at the middle of the linked list using System; public class LinkedList { static Node head; // head of list /* Node Class */ class Node { public int data; public Node next; // Constructor to create a new node public Node(int d) { data = d; next = null; } } // function to insert node at the // middle of the linked list static void insertAtMid(int x) { // if list is empty if (head == null) head = new Node(x); else { // get a new node Node newNode = new Node(x); // assign values to the slow // and fast pointers Node slow = head; Node fast = head.next; while (fast != null && fast.next != null) { // move slow pointer to next node slow = slow.next; // move fast pointer two nodes // at a time fast = fast.next.next; } // insert the 'newNode' and adjust // the required links newNode.next = slow.next; slow.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } } // Driver code public static void Main (String[] args) { // Creating the list 1.2.4.5 head = null; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); Console.WriteLine("Linked list before"+ " insertion: "); display(); int x = 3; insertAtMid(x); Console.WriteLine("\nLinked list after"+ " insertion: "); display(); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to insert node // at the middle of the linked list var head; // head of list /* Node Class */ class Node { // Constructor to create a new node constructor(val) { this.data = val; this.next = null; } } // function to insert node at the // middle of the linked list function insertAtMid(x) { // if list is empty if (head == null) head = new Node(x); else { // get a new node var newNode = new Node(x); // assign values to the slow // and fast pointers var slow = head; var fast = head.next; while (fast != null && fast.next != null) { // move slow pointer to next node slow = slow.next; // move fast pointer two nodes // at a time fast = fast.next.next; } // insert the 'newNode' and adjust // the required links newNode.next = slow.next; slow.next = newNode; } } // function to display the linked list function display() { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } } // Driver program to test above // Creating the list 1.2.4.5 head = null; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); document.write( "Linked list before" + " insertion: " ); display(); var x = 3; insertAtMid(x); document.write( "<br/>Linked list after" + " insertion: " ); display(); // This code is contributed by todaysgaurav </script> |
Output
Linked list before insertion: 1 2 4 5 Linked list after insertion: 1 2 3 4 5
Time Complexity: O(N), Using a loop to traverse n times. Where n is the number of nodes in the linked list.
Auxiliary Space: O(1)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!