You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
Example 2:
Input: lists = [] Output: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] is sorted in ascending order.lists[i].length won't exceed 10^4.
The description was taken from https://leetcode.com/problems/merge-k-sorted-lists/.
#Heap#O(N(Log(N))) Time, O(N) Spaceclass Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: if not lists: return None heap = [] for node in lists: if node: heap.append(node.val) while node.next: node = node.next heap.append(node.val) if not heap: return heapq.heapify(heap) merger = head = ListNode(heapq.heappop(heap)) while heap: value = heapq.heappop(heap) merger.next = ListNode(value) merger = merger.next return head#Merge Sort#O(N(Log(N))) Time, O(N) Spaceclass Solution(object): def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
left= self.mergeKLists(lists[:mid])
right = self.mergeKLists(lists[mid:])
return self.merge(left, right) def merge(self, left:ListNode, right:ListNode) -> ListNode: dummy = merger = ListNode(0) while left and right: if left.val < right.val: merger.next = left left = left.next else: merger.next = right right = right.next merger = merger.next merger.next = left or right return dummy.nextThere's a lot of buzzwords that come to mind when thinking about this solution. We might think, "sorted", "get minimum", "find next minimum", things like that. With these buzzwords, a heap might be the intuitive way to go.
What we can do is push each node value into a heap then pop each value off of the heap and throw them into a new merged, sorted linked list.
First off, if the input of lists is empty then we have nothing to merge and nothing to return.
if not lists: return None
Let's start by initializing our heap from a list.
heap = []
We will then iterate through the heads of each list.
for node in lists:
Remember, the input list is given as a matrix, for example:[[1,4,5],[1,3,4],[2,6]].
What we are doing here in this loop is iterating through the first node, the head, of each of these three lists.
If the head is not a null value, meaning we haven't received an empty list, we will append the head's value to the heap.
if node: heap.append(node.val)
The reason why we have to append the node value and not the node itself is that the heap would have no way to compare two list nodes from its built-in comparator from the heapify method.
Afterward, we will iterate through the remainder of the current head's next nodes to append their values to the heap as well.
while node.next: node = node.next heap.append(node.val)
At this point, if we have nothing in our heap, then before we heapify and try to merge a new list, we can just return here.
This step isn't required but it is a good optimization.
if not heap: return
Here is where the heap's practicality comes into play.
We will heapify the heap so that it is sorted in ascending order, with the minimum node value being at the top.
heapq.heapify(heap)
After that, we just need to merge the node values back into our sorted output linked list.
To do this, we will create a head by popping the top value off of the top of the heap. We will also set a merger pointer initialized to it that will be used to iterate through the list we are creating.
merger = head = ListNode(heapq.heappop(heap))
While the heap isn't empty, we will continue to pop the top node value off, create a new node from the value, merge it into the list, and move the merger pointer to the right.
while heap: value = heapq.heappop(heap) merger.next = ListNode(value) merger = merger.next
After we have merged the lists, we will return the new head.
return head
Alternatively, we see the problem buzzword, "merge", so we can also try a divide and conquer approach by performing a Merge Sort on the input of linked lists that will do everything in place.
The main function we are given, mergeKLists, we will use to recursively break all of our lists into single nodes.
Being a recursive function, we need to remember to set our base cases.
If a function call has gotten an empty list as an input, which will end up happening often during the recursion, we will return none since there are no nodes we will be merging from the input.
if not lists: return None
If a function call has gotten a list input with the length of one, that means we have successfully broken a list partition into a single node. If that happens, we will pass the node back up to the parent recursive call.
if len(lists) == 1: return lists[0]
If a function call has a list that has a length greater than one, then that means we still need to break it up more.
What we will do is find the midpoint of a current function call's input list, then create a left partition ending at the element directly before the mid element, and a right partition starting from the mid element and spanning to the remainder of the list.
mid = len(lists) // 2 left= self.mergeKLists(lists[:mid]) right = self.mergeKLists(lists[mid:])
Once the lists have been broken down into single nodes, we will begin to merge the nodes together by passing them into a merge function we need to build.
return self.merge(left, right)
We will also need a merge function. This is the same function used in the solution of Merge Two Sorted Lists.
This function will take a left and right sublist, initially a single node since that is the size we broke the problem's initial list into, and it will use a pointer to sort the nodes in ascending order before returning a sorted sublist. That sublist will be compared against other sublists returned from this function in the future and that is how the overall linked list will be sorted.
def merge(self, left:ListNode, right:ListNode) -> ListNode:
We will start by creating a dummy node and a merger pointer.
The dummy node is created so that we don't have to handle the initial logic of seeing which node should go first in the list.
dummy = merger = ListNode(0)
Next, we will have loop that will run while the current node in both sublists aren't None.
while left and right:
In each iteration, we will compare the two values.
If the left node is less than the right node, we will merge the left node into the output list and increment the left pointer.
if left.val < right.val: merger.next = left left = left.nextOtherwise, we will do the same thing but for the right node.
else: merger.next = right right = right.nextAfter we have merged the lesser node into the output list, we will increment the merger pointer.
merger = merger.next
Once we have broken from the loop, it means that at least one node is None so we will just merge whichever node isn't None into the output list and return it with the node after the dummy node being the head.
merger.next = left or right return dummy.next
Our goal is to cast a Depth First Search fishing hook down to break the input list into single nodes, then to have those nodes be sorted in the deepest depth of the recursive pond, begin emerging and join together while still sorting, then pop up into our boat as a glorious fifty pound merged, sorted linked list that we can show off in a picture at the bar while wearing a flannel cut-off.