dsa-problem

Merge k sorted lists

Merge all the k linked-lists into one sorted linked-list and return it

Problem

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.length
  • 0 <= k <= 104
  • 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 will not exceed 10^4.

Test Cases

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

See the problem

​

Solution

Solution 1: Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ans = node = ListNode()
        hp = list()
        continue_run = True
        remove_none = False
        count = 0
        
        while continue_run:
            if len(lists):
                for i, l in enumerate(lists):
                    if l:
                        heapq.heappush(hp, (l.val, count, l))
                        lists[i] = l.next
                        count += 1
                    else:
                        remove_none = True

                if remove_none:
                    lists = [x for x in lists if x is not None]
                    remove_none = False
            
            if len(hp):
                (_, _, node.next) = heapq.heappop(hp)
                node = node.next
            else:
                continue_run = False
        
        return ans.next

​

Solution 2: Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ans = node = ListNode()
        hp = list()
        count = 0
        
        for l in lists:
            if l:
                heapq.heappush(hp, (l.val, count, l))
                count += 1
                
        while len(hp):          
            (_, _, l) = heapq.heappop(hp)
            if l.next:
                heapq.heappush(hp, (l.next.val, count, l.next))
                count += 1
            node.next = l
            node = l

        
        return ans.next

Here,

  • I use count as a second member for comparison for case when tuples has same l.val

    • I could have used list indices as second member but they could also conflict.
    • Because count will always be unique

  • Time complexity is O(nlogk)

    • Breakup: O(klogk + n+ (n-k)logk))

​