In | Structure for a linked list node ; Given a reference ( pointer to pointer ) to the head of a list and an int , push a new node on the front of the list . ; Allocate node ; Put in the data ; Link the old list off the new node ; Move the head to point to the new node ; Function to merge two sorted linked lists LL1 and LL2 without using any extra space . ; Run till either one of a or b runs out ; For each element of LL1 , compare it with first element of LL2 . ; Swap the two elements involved if LL1 has a greater element ; To keep LL2 sorted , place first element of LL2 at its correct place ; Find mismatch by traversing the second linked list once ; Correct the pointers ; Move LL1 pointer to next element ; Function to print the linked link ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def push ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( ) NEW_LINE new_node . data = new_data NEW_LINE new_node . next = ( head_ref ) NEW_LINE ( head_ref ) = new_node NEW_LINE return head_ref NEW_LINE DEDENT def mergeLists ( a , b ) : NEW_LINE INDENT while ( a and b ) : NEW_LINE INDENT if ( a . data > b . data ) : NEW_LINE INDENT a . data , b . data = b . data , a . data NEW_LINE temp = b NEW_LINE if ( b . next and b . data > b . next . data ) : NEW_LINE INDENT b = b . next NEW_LINE ptr = b NEW_LINE prev = None NEW_LINE while ( ptr and ptr . data < temp . data ) : NEW_LINE INDENT prev = ptr NEW_LINE ptr = ptr . next NEW_LINE DEDENT prev . next = temp NEW_LINE temp . next = ptr NEW_LINE DEDENT DEDENT a = a . next NEW_LINE DEDENT DEDENT def printList ( head ) : NEW_LINE INDENT while ( head ) : NEW_LINE INDENT print ( head . data , end = ' - > ' ) NEW_LINE head = head . next NEW_LINE DEDENT print ( ' NULL ' ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = None NEW_LINE a = push ( a , 10 ) NEW_LINE a = push ( a , 8 ) NEW_LINE a = push ( a , 7 ) NEW_LINE a = push ( a , 4 ) NEW_LINE a = push ( a , 2 ) NEW_LINE b = None NEW_LINE b = push ( b , 12 ) NEW_LINE b = push ( b , 3 ) NEW_LINE b = push ( b , 1 ) NEW_LINE mergeLists ( a , b ) NEW_LINE print ( " First ▁ List : ▁ " , end = ' ' ) NEW_LINE printList ( a ) NEW_LINE print ( " Second ▁ List : ▁ " , end = ' ' ) NEW_LINE printList ( b ) NEW_LINE DEDENT