Merge two unsorted linked lists to get a sorted list | C ++ program for the above approach ; Create structure for a node ; Function to print the linked list ; Store the head of the linked list into a temporary node * and iterate ; Function takes the head of the LinkedList and the data as argument and if no LinkedList exists , it creates one with the head pointing to first node . If it exists already , it appends given node at end of the last node ; Create a new node ; Insert data into the temporary node and point it 's next to NULL ; Check if head is null , create a linked list with temp as head and tail of the list ; Else insert the temporary node after the tail of the existing node and make the temporary node as the tail of the linked list ; Return the list ; Function to concatenate the two lists ; Iterate through the head1 to find the last node join the next of last node of head1 to the 1 st node of head2 ; return the concatenated lists as a single list - head1 ; Sort the linked list using bubble sort ; Compares two adjacent elements and swaps if the first element is greater than the other one . ; Driver Code ; Given Linked List 1 ; Given Linked List 2 ; Merge the two lists in a single list ; Sort the unsorted merged list ; Print the final sorted merged list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { int data ; node * next ; } ; void setData ( node * head ) { node * tmp ; tmp = head ; while ( tmp != NULL ) { cout << tmp -> data << " ▁ - > ▁ " ; tmp = tmp -> next ; } } node * getData ( node * head , int num ) { node * temp = new node ; node * tail = head ; temp -> data = num ; temp -> next = NULL ; if ( head == NULL ) { head = temp ; tail = temp ; } else { while ( tail != NULL ) { if ( tail -> next == NULL ) { tail -> next = temp ; tail = tail -> next ; } tail = tail -> next ; } } return head ; } node * mergelists ( node * * head1 , node * * head2 ) { node * tail = * head1 ; while ( tail != NULL ) { if ( tail -> next == NULL && head2 != NULL ) { tail -> next = * head2 ; break ; } tail = tail -> next ; } return * head1 ; } void sortlist ( node * * head1 ) { node * curr = * head1 ; node * temp = * head1 ; while ( curr -> next != NULL ) { temp = curr -> next ; while ( temp != NULL ) { if ( temp -> data < curr -> data ) { int t = temp -> data ; temp -> data = curr -> data ; curr -> data = t ; } temp = temp -> next ; } curr = curr -> next ; } } int main ( ) { node * head1 = new node ; node * head2 = new node ; head1 = NULL ; head2 = NULL ; head1 = getData ( head1 , 4 ) ; head1 = getData ( head1 , 7 ) ; head1 = getData ( head1 , 5 ) ; head2 = getData ( head2 , 2 ) ; head2 = getData ( head2 , 1 ) ; head2 = getData ( head2 , 8 ) ; head2 = getData ( head2 , 1 ) ; head1 = mergelists ( & head1 , & head2 ) ; sortlist ( & head1 ) ; setData ( head1 ) ; return 0 ; }