Merge k sorted lists

Problem Statement

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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:

1
2
Input: lists = []
Output: []

Example 3:

1
2
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
2
3
4
[[1,4,5],[1,3,4],[2,6]]
[]
[[]]
[[1,2,2],[1,1,2]]

See the problem

Solution

Solution 1: Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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))