Merge two unsorted linked lists to get a sorted list | 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
class node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def setData ( head ) : NEW_LINE INDENT tmp = head NEW_LINE while ( tmp != None ) : NEW_LINE INDENT print ( tmp . data , end = " ▁ - > ▁ " ) NEW_LINE tmp = tmp . next NEW_LINE DEDENT DEDENT def getData ( head , num ) : NEW_LINE INDENT temp = node ( - 1 ) NEW_LINE tail = head NEW_LINE temp . data = num NEW_LINE temp . next = None NEW_LINE if ( head == None ) : NEW_LINE INDENT head = temp NEW_LINE tail = temp NEW_LINE DEDENT else : NEW_LINE INDENT while ( tail != None ) : NEW_LINE INDENT if ( tail . next == None ) : NEW_LINE INDENT tail . next = temp NEW_LINE tail = tail . next NEW_LINE DEDENT tail = tail . next NEW_LINE DEDENT DEDENT return head NEW_LINE DEDENT def mergelists ( head1 , head2 ) : NEW_LINE INDENT tail = head1 NEW_LINE while ( tail != None ) : NEW_LINE INDENT if ( tail . next == None and head2 != None ) : NEW_LINE INDENT tail . next = head2 NEW_LINE break NEW_LINE DEDENT tail = tail . next NEW_LINE DEDENT return head1 NEW_LINE DEDENT def sortlist ( head1 ) : NEW_LINE INDENT curr = head1 NEW_LINE temp = head1 NEW_LINE while ( curr . next != None ) : NEW_LINE INDENT temp = curr . next NEW_LINE while ( temp != None ) : NEW_LINE INDENT if ( temp . data < curr . data ) : NEW_LINE INDENT t = temp . data NEW_LINE temp . data = curr . data NEW_LINE curr . data = t NEW_LINE DEDENT temp = temp . next NEW_LINE DEDENT curr = curr . next NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT head1 = node ( - 1 ) NEW_LINE head2 = node ( - 1 ) NEW_LINE head1 = None NEW_LINE head2 = None NEW_LINE head1 = getData ( head1 , 4 ) NEW_LINE head1 = getData ( head1 , 7 ) NEW_LINE head1 = getData ( head1 , 5 ) NEW_LINE head2 = getData ( head2 , 2 ) NEW_LINE head2 = getData ( head2 , 1 ) NEW_LINE head2 = getData ( head2 , 8 ) NEW_LINE head2 = getData ( head2 , 1 ) NEW_LINE head1 = mergelists ( head1 , head2 ) NEW_LINE sortlist ( head1 ) NEW_LINE setData ( head1 ) NEW_LINE DEDENT