Problem
You are given an array of k linked lists, each sorted ascending. Merge all into one sorted linked list.
Example
Input: [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]Solution
Min-heap of (value, list index). Pop smallest, push next from same list. Total work O(N log k).
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
tail = dummy
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextfunction mergeKLists(lists) {
// Simple priority queue using array sort
const heap = lists.filter(l => l).map(l => ({ val: l.val, node: l }));
heap.sort((a, b) => a.val - b.val);
const dummy = { next: null };
let tail = dummy;
while (heap.length) {
const { node } = heap.shift();
tail.next = node;
tail = tail.next;
if (node.next) {
const newItem = { val: node.next.val, node: node.next };
let i = 0;
while (i < heap.length && heap[i].val < newItem.val) i++;
heap.splice(i, 0, newItem);
}
}
return dummy.next;
}ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (auto l : lists) if (l) pq.push(l);
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top(); pq.pop();
tail->next = node;
tail = tail->next;
if (node->next) pq.push(node->next);
}
return dummy.next;
}public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode l : lists) if (l != null) pq.offer(l);
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
tail.next = node;
tail = tail.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}Complexity
- Time: O(N log k)
- Space: O(k)
Explanation
Heap holds at most k elements (one per list). Each of the N total nodes is pushed and popped once.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?