Just use merge sort's idea to divide k lists and merge each two lists recursively. Time complexity is O(nlogk) assuming n is the total number of nodes.
def mergeKLists(self, lists): def merge(l1, l2): p = head = ListNode(0) # dummy node while l1 or l2: if l1 and l2: if l1.val <= l2.val: p.next = l1 l1 = l1.next else: p.next = l2 l2 = l2.next p = p.next elif l1 is None: p.next = l2 break elif l2 is None: p.next = l1 break return head.next def divide(lists, start, end): if start == end: return lists[start] mid = start + (end - start) / 2 l1 = divide(lists, start, mid) l2 = divide(lists, mid + 1, end) return merge(l1, l2) return divide(lists, 0, len(lists) - 1) if lists else 
Use a heap of size k to pop the smallest element from each list and push the next element into the heap util every element is in and out from the heap.
def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ import heapq p = dummy = ListNode(-1) h =  for i in range(len(lists)): if lists[i] > 0: heapq.heappush(h, (lists[i].val, lists[i])) while h: curr = heapq.heappop(h) currlist = curr p.next = currlist p = p.next if currlist.next: heapq.heappush(h, (currlist.next.val, currlist.next)) return dummy.next