leetcode_gym/_problems/mergeKSortedLinkedLists.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Merge K Sorted Linked Lists	2020-08-09	heap	https://leetcode.com/problems/merge-k-sorted-lists/	Solved

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution

1. Push all elements into a minHeap.
2. Pop them out and create a new linked list.

time is O(n*logk) where n=total number of elements in k list

• because each insert into minheap is logk, and we do it n times for each element

space is O(n) to hold all elements in minHeap

{% highlight python %}

def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """

minHeap = []

# push all elements into minHeap
for currList in lists:
    
    head = currList
    
    while head:
        heapq.heappush(minHeap, head.val)
        head = head.next


# pop all elements from minHeap (and craete new linked list)
dummy = ListNode(0)
head = dummy

while minHeap:
    head.next = ListNode( heapq.heappop(minHeap) )
    head = head.next
    
return dummy.next

{% endhighlight %}