Merge two unsorted linked lists to get a sorted list | Java 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
class GFG { static node head1 = null ; static node head2 = null ; static class node { int data ; node next ; } ; static void setData ( node head ) { node tmp ; tmp = head ; while ( tmp != null ) { System . out . print ( tmp . data + " ▁ - > ▁ " ) ; tmp = tmp . next ; } } static 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 ; } static node mergelists ( ) { node tail = head1 ; while ( tail != null ) { if ( tail . next == null && head2 != null ) { tail . next = head2 ; break ; } tail = tail . next ; } return head1 ; } static void sortlist ( ) { 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 ; } } public static void main ( String [ ] args ) { 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 ( ) ; sortlist ( ) ; setData ( head1 ) ; } }