Merge K sorted linked lists | Set 1 | A Linked List node ; Function to prnodes in a given linked list ; The main function that takes an array of lists arr [ 0. . last ] and generates the sorted output ; Traverse form second list to last ; head of both the lists , 0 and ith list . ; Break if list ended ; Smaller than first element ; Traverse the first list ; Smaller than next element ; go to next node ; if last node ; Driver code ; Number of linked lists ; Number of elements in each list ; an array of pointers storing the head nodes of the linked lists ; Merge all lists
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 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 mergeKLists ( arr , last ) : NEW_LINE INDENT for i in range ( 1 , last + 1 ) : NEW_LINE INDENT while ( True ) : NEW_LINE INDENT head_0 = arr [ 0 ] NEW_LINE head_i = arr [ i ] NEW_LINE if ( head_i == None ) : NEW_LINE INDENT break NEW_LINE DEDENT if ( head_0 . data >= head_i . data ) : NEW_LINE INDENT arr [ i ] = head_i . next NEW_LINE head_i . next = head_0 NEW_LINE arr [ 0 ] = head_i NEW_LINE DEDENT else : NEW_LINE INDENT while ( head_0 . next != None ) : NEW_LINE INDENT if ( head_0 . next . data >= head_i . data ) : NEW_LINE INDENT arr [ i ] = head_i . next NEW_LINE head_i . next = head_0 . next NEW_LINE head_0 . next = head_i NEW_LINE break NEW_LINE DEDENT head_0 = head_0 . next NEW_LINE if ( head_0 . next == None ) : NEW_LINE INDENT arr [ i ] = head_i . next NEW_LINE head_i . next = None NEW_LINE head_0 . next = head_i NEW_LINE head_0 . next . next = None NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT return arr [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT k = 3 NEW_LINE n = 4 NEW_LINE arr = [ None for i in range ( k ) ] NEW_LINE arr [ 0 ] = Node ( 1 ) NEW_LINE arr [ 0 ] . next = Node ( 3 ) NEW_LINE arr [ 0 ] . next . next = Node ( 5 ) NEW_LINE arr [ 0 ] . next . next . next = Node ( 7 ) NEW_LINE arr [ 1 ] = Node ( 2 ) NEW_LINE arr [ 1 ] . next = Node ( 4 ) NEW_LINE arr [ 1 ] . next . next = Node ( 6 ) NEW_LINE arr [ 1 ] . next . next . next = Node ( 8 ) NEW_LINE arr [ 2 ] = Node ( 0 ) NEW_LINE arr [ 2 ] . next = Node ( 9 ) NEW_LINE arr [ 2 ] . next . next = Node ( 10 ) NEW_LINE arr [ 2 ] . next . next . next = Node ( 11 ) NEW_LINE head = mergeKLists ( arr , k - 1 ) NEW_LINE printList ( head ) NEW_LINE DEDENT