Back to DSA
Merge K Sorted Lists
hardYou have k linked lists, each individually sorted in non-decreasing order. Combine them all into a single sorted linked list and return it.
Examples
Example 1:
Input:
lists = [[2,5,8],[1,4,6],[3,7]]Output:
[1,2,3,4,5,6,7,8] Example 2:
Input:
lists = [[]]Output:
[]Hints
import java.util.*;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) pq.offer(node);
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
curr.next = node;
curr = curr.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}
}Time complexity
O(n log k)Space complexity
O(1)