Merge two sorted lists ( in | C ++ program to merge two sorted linked lists in - place . ; Linked List node ; Function to create newNode in a linkedlist ; A utility function to print linked list ; Merges two lists with headers as h1 and h2 . It assumes that h1 ' s ▁ data ▁ is ▁ smaller ▁ than ▁ or ▁ equal ▁ to ▁ h2' s data . ; if only one node in first list simply point its head to second list ; Initialize current and next pointers of both lists ; if curr2 lies in between curr1 and next1 then do curr1 -> curr2 -> next1 ; now let curr1 and curr2 to point to their immediate next pointers ; if more nodes in first list ; else point the last node of first list to the remaining nodes of second list ; Merges two given lists in - place . This function mainly compares head nodes and calls mergeUtil ( ) ; start with the linked list whose head data is the least ; Driver program ; 1 -> 3 -> 5 LinkedList created ; 0 -> 2 -> 4 LinkedList created
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; struct Node * newNode ( int key ) { struct Node * temp = new Node ; temp -> data = key ; temp -> next = NULL ; return temp ; } void printList ( struct Node * node ) { while ( node != NULL ) { printf ( " % d ▁ " , node -> data ) ; node = node -> next ; } } struct Node * mergeUtil ( struct Node * h1 , struct Node * h2 ) { if ( ! h1 -> next ) { h1 -> next = h2 ; return h1 ; } struct Node * curr1 = h1 , * next1 = h1 -> next ; struct Node * curr2 = h2 , * next2 = h2 -> next ; while ( next1 && curr2 ) { if ( ( curr2 -> data ) >= ( curr1 -> data ) && ( curr2 -> data ) <= ( next1 -> data ) ) { next2 = curr2 -> next ; curr1 -> next = curr2 ; curr2 -> next = next1 ; curr1 = curr2 ; curr2 = next2 ; } else { if ( next1 -> next ) { next1 = next1 -> next ; curr1 = curr1 -> next ; } else { next1 -> next = curr2 ; return h1 ; } } } return h1 ; } struct Node * merge ( struct Node * h1 , struct Node * h2 ) { if ( ! h1 ) return h2 ; if ( ! h2 ) return h1 ; if ( h1 -> data < h2 -> data ) return mergeUtil ( h1 , h2 ) ; else return mergeUtil ( h2 , h1 ) ; } int main ( ) { struct Node * head1 = newNode ( 1 ) ; head1 -> next = newNode ( 3 ) ; head1 -> next -> next = newNode ( 5 ) ; struct Node * head2 = newNode ( 0 ) ; head2 -> next = newNode ( 2 ) ; head2 -> next -> next = newNode ( 4 ) ; struct Node * mergedhead = merge ( head1 , head2 ) ; printList ( mergedhead ) ; return 0 ; }