You are given an array of
lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
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
Input: lists =  Output: 
Input: lists = [] Output: 
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
import pytest from .util import toListNode, toList from .Day24_MergeKSortedLists import Solution s = Solution() @pytest.mark.parametrize( "lists,expected", [([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]), (, ), ([], )], ) def test_merge_k_lists(lists, expected): assert toList(s.mergeKLists(list(map(lambda x: toListNode(x), lists)))) == expected @pytest.mark.parametrize( "lists,expected", [([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]), (, ), ([], )], ) def test_merge_k_lists2(lists, expected): assert toList(s.mergeKLists2(list(map(lambda x: toListNode(x), lists)))) == expected
from typing import List from .util import ListNode from queue import PriorityQueue def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: head = ListNode() current = head while l1 and l2: if l1.val <= l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l1 l1 = current.next.next current = current.next current.next = l2 if l2 else l1 return head.next class Solution: def build_queue(self, lists: List[ListNode]) -> PriorityQueue: q = PriorityQueue() for l in lists: if l: q.put((l.val, l)) return q def mergeKLists2(self, lists: List[ListNode]) -> ListNode: head = ListNode() current = head q = self.build_queue(lists) while not q.empty(): val, list_node = q.get() current.next = ListNode(val) current = current.next next_node = list_node.next if next_node: q.put((next_node.val, next_node)) return head.next def mergeKLists(self, lists: List[ListNode]) -> ListNode: k = len(lists) if k == 0: return None step = 1 while step < k: for i in range(0, k - step, step * 2): lists[i] = mergeTwoLists(lists[i], lists[i + step]) step *= 2 return lists
This seemed like a good place to use a PriorityQueue to me but I couldn't get it to work in leetcode as the ListNode class did not implement
__lt__. I have left an example in the code called
The solution I went with was kind of cheating. I more or less copied the solution from Day 4. I improved it a little but basically we are breaking the problem down into merging 2 sorted lists.
We merge in steps to basically merge in pairs. Eventually you get all lists merged.
The runtime is about
O(n log k) where k =
len(lists). We don't use up any extra space.