Merge k Sorted Lists Problem

Question

Given an array of linked-lists lists, each linked list is sorted in ascending order.

Merge all the linked-lists into one sort 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

 

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

Answer 1

Here we will use a min heap , the property of min heap is that it gives the min element in heap in O(1) ie top of the heap.
So initally we will be pushing every node in the heap one by one and then make a new linked list by poping top of heap till the heap is empty.

# Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next from heapq import * class Solution:     def mergeKLists(self, lists: List[ListNode]) -> ListNode:         min_heap = []         heapify(min_heap)                  for link in lists:             while link:                 heappush(min_heap, link.val)                 link = link.next                  head = ListNode(0)         temp = head         while min_heap:             temp.next = ListNode(heappop(min_heap))             temp = temp.next                  return head.next

eg : lists = [[1,4,5],[1,3,4],[2,6]]

ans = Solution()

ans.mergeKLists(lists)

output :

[1,1,2,3,4,4,5,6]