#NEWLINE# def mergeKLists_TLE1( self , lists ) : #NEWLINE# #INDENT# '\n        k lists; each list has N items\n        Algorithm 1:\n        Merge the lists 1 by 1, just add a loop outside the merge.\n        Complexity: 2N+3N+4N+..kN = O(k^2 * N)\n\n        Algorithm 2:\n        Group the lists in pairs with every pair having 2 lists, merge two, then repeat again\n        Complexity:\n        T(N) = (k/2)*2N+(k/4)*4N..+(k/2^r)*2^r*N\n        T(N) = O(lg k * k * N)\n\n        :param lists: a list of ListNode\n        :return: ListNode\n        ' #NEWLINE# lists = filter ( ( lambda x : ( x is not None ) ) , lists ) #NEWLINE# if ( not lists ) : #NEWLINE# #INDENT# return #NEWLINE# #UNINDENT# length = len ( lists ) #NEWLINE# factor = 2 #NEWLINE# while ( length > 0 ) : #NEWLINE# #INDENT# i = 0 #NEWLINE# while True : #NEWLINE# #INDENT# try : #NEWLINE# #INDENT# lists [ i ] = self . mergeTwoLists ( lists [ i ] , lists [ ( i + ( factor / 2 ) ) ] ) #NEWLINE# #UNINDENT# except IndexError : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# i += factor #NEWLINE# #UNINDENT# length /= 2 #NEWLINE# factor *= 2 #NEWLINE# #UNINDENT# return lists [ 0 ]