text: Insert node into the middle of the linked list | C ++ implementation to insert node at the middle of the linked list ; structure of a node ; function to create and return a node ; function to insert node at the middle of the linked list ; if list is empty ; get a new node ; calculate length of the linked list , i . e , the number of nodes ; ' count ' the number of nodes after which the new node is to be inserted ; ' ptr ' points to the node after which the new node is to be inserted ; insert the ' newNode ' and adjust the required links ; function to display the linked list ; Driver program to test above ; Creating the list 1 -> 2 -> 4 -> 5
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * next ; } ; Node * getNode ( int data ) { Node * newNode = ( Node * ) malloc ( sizeof ( Node ) ) ; newNode -> data = data ; newNode -> next = NULL ; return newNode ; } void insertAtMid ( Node * * head_ref , int x ) { if ( * head_ref == NULL ) * head_ref = getNode ( x ) ; else { Node * newNode = getNode ( x ) ; Node * ptr = * head_ref ; int len = 0 ; while ( ptr != NULL ) { len ++ ; ptr = ptr -> next ; } int count = ( ( len % 2 ) == 0 ) ? ( len / 2 ) : ( len + 1 ) / 2 ; ptr = * head_ref ; while ( count -- > 1 ) ptr = ptr -> next ; newNode -> next = ptr -> next ; ptr -> next = newNode ; } } void display ( Node * head ) { while ( head != NULL ) { cout << head -> data << " ▁ " ; head = head -> next ; } } int main ( ) { 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 << " Linked list after insertion : " display ( head ) ; return 0 ; }