Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
Merge two list
This problem rings a bell about a simpler version of the problem: merge 2 lists. We might need to use it later.
def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ new_dummy_head = ListNode(1) cur_ptr = new_dummy_head while l1 and l2: if l1.val < l2.val: cur_ptr.next = l1 l1 = l1.next else: cur_ptr.next = l2 l2 = l2.next cur_ptr = cur_ptr.next if not l1: cur_ptr.next = l2 if not l2: cur_ptr.next = l1 return new_dummy_head.next
Combine one by one
We will call mergeTwoList k – 1 times and return the head.
def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None if len(lists) == 1: return lists dummy_head = lists for i in range(1, len(lists)): dummy_head = self.mergeTwoLists(dummy_head, lists[i]) return dummy_head
Since mergeTwoLists only alter next pointers of node, the space complexity is O(1).
Let the number of total node be N and the number of linked list be k.
We need to call mergeTwoList k – 1 times. And in the worst case, we need to traverse over the longer linked list of the two. Assuming the length of each linked list is equal, the longer linked list will have length of n / k, 2n / k … (k – 1)n/k. So the run time is
Divide and conquer
Divide and conquer is a problem solving patterns that combine solutions of smaller instance to find the solution of the bigger problem.
In this problem, merge k linked list can become merging k // 2 linked lists who are the result of merging pairs of linked list.
def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None if len(lists) == 1: return lists head_1 = self.mergeKLists(lists[:len(lists) // 2]) head_2 = self.mergeKLists(lists[len(lists) // 2:]) h = self.mergeTwoLists(head_1, head_2) return h
We have k linked list, so we will merge at most logk times. In the worst case scenario, the length of the longer linked list is O(n). So The run time is O(n log k).