In | C ++ Program to merge two sorted linked lists without using any extra space and without changing links of first list ; Structure for a linked list node ; Given a reference ( pointer to pointer ) to the head of a list and an int , push a new node on the front of the list . ; allocate node ; put in the data ; link the old list off the new node ; move the head to point to the new node ; Function to merge two sorted linked lists LL1 and LL2 without using any extra space . ; run till either one of a or b runs out ; for each element of LL1 , compare it with first element of LL2 . ; swap the two elements involved if LL1 has a greater element ; To keep LL2 sorted , place first element of LL2 at its correct place ; find mismatch by traversing the second linked list once ; correct the pointers ; move LL1 pointer to next element ; Code to print the linked link ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; new_node -> data = new_data ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } void mergeLists ( struct Node * a , struct Node * & b ) { while ( a && b ) { if ( a -> data > b -> data ) { swap ( a -> data , b -> data ) ; struct Node * temp = b ; if ( b -> next && b -> data > b -> next -> data ) { b = b -> next ; struct Node * ptr = b , * prev = NULL ; while ( ptr && ptr -> data < temp -> data ) { prev = ptr ; ptr = ptr -> next ; } prev -> next = temp ; temp -> next = ptr ; } } a = a -> next ; } } void printList ( struct Node * head ) { while ( head ) { cout << head -> data << " - > " ; head = head -> next ; } cout << " NULL " << endl ; } int main ( ) { struct Node * a = NULL ; push ( & a , 10 ) ; push ( & a , 8 ) ; push ( & a , 7 ) ; push ( & a , 4 ) ; push ( & a , 2 ) ; struct Node * b = NULL ; push ( & b , 12 ) ; push ( & b , 3 ) ; push ( & b , 1 ) ; mergeLists ( a , b ) ; cout << " First ▁ List : ▁ " ; printList ( a ) ; cout << " Second ▁ List : ▁ " ; printList ( b ) ; return 0 ; }