Merge two sorted lists ( in | 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
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( 0 ) NEW_LINE temp . data = key NEW_LINE temp . next = None NEW_LINE return temp NEW_LINE DEDENT def printList ( node ) : NEW_LINE INDENT while ( node != None ) : NEW_LINE INDENT print ( node . data , end = " ▁ " ) NEW_LINE node = node . next NEW_LINE DEDENT DEDENT def mergeUtil ( h1 , h2 ) : NEW_LINE INDENT if ( h1 . next == None ) : NEW_LINE INDENT h1 . next = h2 NEW_LINE return h1 NEW_LINE DEDENT curr1 = h1 NEW_LINE next1 = h1 . next NEW_LINE curr2 = h2 NEW_LINE next2 = h2 . next NEW_LINE while ( next1 != None and curr2 != None ) : NEW_LINE INDENT if ( ( curr2 . data ) >= ( curr1 . data ) and ( curr2 . data ) <= ( next1 . data ) ) : NEW_LINE INDENT next2 = curr2 . next NEW_LINE curr1 . next = curr2 NEW_LINE curr2 . next = next1 NEW_LINE curr1 = curr2 NEW_LINE curr2 = next2 NEW_LINE DEDENT else : NEW_LINE INDENT if ( next1 . next ) : NEW_LINE INDENT next1 = next1 . next NEW_LINE curr1 = curr1 . next NEW_LINE DEDENT else : NEW_LINE INDENT next1 . next = curr2 NEW_LINE return h1 NEW_LINE DEDENT DEDENT DEDENT return h1 NEW_LINE DEDENT def merge ( h1 , h2 ) : NEW_LINE INDENT if ( h1 == None ) : NEW_LINE INDENT return h2 NEW_LINE DEDENT if ( h2 == None ) : NEW_LINE INDENT return h1 NEW_LINE DEDENT if ( h1 . data < h2 . data ) : NEW_LINE INDENT return mergeUtil ( h1 , h2 ) NEW_LINE DEDENT else : NEW_LINE INDENT return mergeUtil ( h2 , h1 ) NEW_LINE DEDENT DEDENT head1 = newNode ( 1 ) NEW_LINE head1 . next = newNode ( 3 ) NEW_LINE head1 . next . next = newNode ( 5 ) NEW_LINE head2 = newNode ( 0 ) NEW_LINE head2 . next = newNode ( 2 ) NEW_LINE head2 . next . next = newNode ( 4 ) NEW_LINE mergedhead = merge ( head1 , head2 ) NEW_LINE printList ( mergedhead ) NEW_LINE