Merge K sorted Doubly Linked List in Sorted Order | A linked list node ; Given a reference ( pointer to pointer ) to the head Of a DLL and an int , appends a new node at the end ; Allocate node ; Put in the data ; This new node is going to be the last node , so make next of it as None ; If the Linked List is empty , then make the new node as head ; Else traverse till the last node ; Change the next of last node ; Make last node as previous of new node ; Function to print the list ; Run while loop unless node becomes None ; Function to merge two sorted doubly linked lists ; If any of the list is empty ; Comparison the data of two linked list ; Store head pointer before merge the list ; Changing of pointer between Two list for merging ; Changing of pointer between Two list for merging ; Condition to check if any anyone list not end ; Return head pointer of merged list ; Function to merge all sorted linked list in sorted order ; Function call to merge two sorted doubly linked list at a time ; Return final sorted doubly linked list ; Driver code ; Loop to initialize all the lists to empty ; Create first doubly linked List List1 . 1 <= > 5 <= > 9 ; Create second doubly linked List List2 . 2 <= > 3 <= > 7 <= > 12 ; Create third doubly linked List List3 . 8 <= > 11 <= > 13 <= > 18 ; Function call to merge all sorted doubly linked lists in sorted order ; Print final sorted list
class Node : NEW_LINE INDENT def __init__ ( self , new_data ) : NEW_LINE INDENT self . data = new_data NEW_LINE self . next = None NEW_LINE self . prev = None NEW_LINE DEDENT DEDENT def append ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( 0 ) NEW_LINE last = head_ref NEW_LINE new_node . data = new_data NEW_LINE new_node . next = None NEW_LINE if ( head_ref == None ) : NEW_LINE INDENT new_node . prev = None NEW_LINE head_ref = new_node NEW_LINE return head_ref NEW_LINE DEDENT while ( last . next != None ) : NEW_LINE INDENT last = last . next NEW_LINE DEDENT last . next = new_node NEW_LINE new_node . prev = last NEW_LINE return head_ref NEW_LINE DEDENT def printList ( node ) : NEW_LINE INDENT last = None NEW_LINE while ( node != None ) : NEW_LINE INDENT print ( node . data , end = " ▁ " ) NEW_LINE last = node NEW_LINE node = node . next NEW_LINE DEDENT DEDENT def mergeList ( p , q ) : NEW_LINE INDENT s = None NEW_LINE if ( p == None or q == None ) : NEW_LINE INDENT if ( p == None ) : NEW_LINE INDENT return q NEW_LINE DEDENT else : NEW_LINE INDENT return p NEW_LINE DEDENT DEDENT if ( p . data < q . data ) : NEW_LINE INDENT p . prev = s NEW_LINE s = p NEW_LINE p = p . next NEW_LINE DEDENT else : NEW_LINE INDENT q . prev = s NEW_LINE s = q NEW_LINE q = q . next NEW_LINE DEDENT head = s NEW_LINE while ( p != None and q != None ) : NEW_LINE INDENT if ( p . data < q . data ) : NEW_LINE INDENT s . next = p NEW_LINE p . prev = s NEW_LINE s = s . next NEW_LINE p = p . next NEW_LINE DEDENT else : NEW_LINE INDENT s . next = q NEW_LINE q . prev = s NEW_LINE s = s . next NEW_LINE q = q . next NEW_LINE DEDENT DEDENT if ( p == None ) : NEW_LINE INDENT s . next = q NEW_LINE q . prev = s NEW_LINE DEDENT if ( q == None ) : NEW_LINE INDENT s . next = p NEW_LINE p . prev = s NEW_LINE DEDENT return head NEW_LINE DEDENT def mergeAllList ( head , k ) : NEW_LINE INDENT finalList = None NEW_LINE i = 0 NEW_LINE while ( i < k ) : NEW_LINE INDENT finalList = mergeList ( finalList , head [ i ] ) NEW_LINE i = i + 1 NEW_LINE DEDENT return finalList NEW_LINE DEDENT k = 3 NEW_LINE head = [ 0 ] * k NEW_LINE i = 0 NEW_LINE while ( i < k ) : NEW_LINE INDENT head [ i ] = None NEW_LINE i = i + 1 NEW_LINE DEDENT head [ 0 ] = append ( head [ 0 ] , 1 ) NEW_LINE head [ 0 ] = append ( head [ 0 ] , 5 ) NEW_LINE head [ 0 ] = append ( head [ 0 ] , 9 ) NEW_LINE head [ 1 ] = append ( head [ 1 ] , 2 ) NEW_LINE head [ 1 ] = append ( head [ 1 ] , 3 ) NEW_LINE head [ 1 ] = append ( head [ 1 ] , 7 ) NEW_LINE head [ 1 ] = append ( head [ 1 ] , 12 ) NEW_LINE head [ 2 ] = append ( head [ 2 ] , 8 ) NEW_LINE head [ 2 ] = append ( head [ 2 ] , 11 ) NEW_LINE head [ 2 ] = append ( head [ 2 ] , 13 ) NEW_LINE head [ 2 ] = append ( head [ 2 ] , 18 ) NEW_LINE finalList = mergeAllList ( head , k ) NEW_LINE printList ( finalList ) NEW_LINE