700265. Merge K sorted linked lists
Medium
Merge K sorted linked lists
Slug: merge-k-sorted-linked-lists
Difficulty: Medium
Id: 700265
Topic Tags: Linked List, Heap, Data Structures
Company Tags: VMWare, Amazon, Microsoft, Oracle
Summary
Given k sorted linked lists, the task is to merge these lists into a single sorted linked list. This problem involves manipulating and combining multiple linked lists while maintaining their original order.
Detailed Explanation
To solve this problem, we can use a priority queue or a heap data structure. The idea is to treat each node of the linked lists as an element in the priority queue. We continuously pop the smallest element from the priority queue and add it to our result list. This process continues until all elements are processed.
Here's a step-by-step breakdown of the solution:
- Create a min-heap.
- Insert all nodes from each of the k linked lists into the heap.
- While the heap is not empty:
- Extract the smallest node from the heap (which will be the next element in our result list).
- If the extracted node has children, insert them into the heap.
- Add the extracted node to our result list.
- Once the heap is empty, return the result list.
Optimized Solutions
Java
import java.util.PriorityQueue;
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) {
queue.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!queue.isEmpty()) {
ListNode node = queue.poll();
current.next = node;
current = current.next;
if (node.next != null) {
queue.offer(node.next);
}
}
return dummy.next;
}
}