You are given an array of
klinked-listslists, 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4-
lists[I]is sorted in ascending order. - The sum of
lists[i].lengthwon't exceed10^4.
Tests
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
Solution
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[0]
Analysis
Commentary
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 __gt__or __lt__. I have left an example in the code called mergeKLists2.
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.
Top comments (0)