Problem Statement
You are given an array of k linked-lists lists, 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.length 0 <= k <= 104 0 <= lists[i].length <= 500 -104 <= lists[i][j] <= 104 lists[i] is sorted in ascending order. The sum of lists[i].length will not exceed 104.
Java Solution
You can solve this problem using a priority queue (min heap) to efficiently merge the lists. Here’s the Java code for merging k sorted linked lists:
import java.util.Comparator;
import java.util.PriorityQueue;
public class MergeKSortedLists {
public static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
// Use a priority queue to keep track of the smallest element at the front
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
// Add the head of each list to the priority queue
for (ListNode list : lists) {
if (list != null) {
minHeap.offer(list);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// Keep popping the smallest element from the priority queue and add its next to the queue
while (!minHeap.isEmpty()) {
ListNode smallest = minHeap.poll();
current.next = smallest;
current = current.next;
if (smallest.next != null) {
minHeap.offer(smallest.next);
}
}
return dummy.next;
}
// Helper method to convert an array of arrays to an array of linked lists
private ListNode[] arraysToLinkedLists(int[][] arrays) {
ListNode[] lists = new ListNode[arrays.length];
for (int i = 0; i < arrays.length; i++) {
lists[i] = arrayToLinkedList(arrays[i]);
}
return lists;
}
// Helper method to convert an array to a linked list
private ListNode arrayToLinkedList(int[] array) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
for (int value : array) {
current.next = new ListNode(value);
current = current.next;
}
return dummy.next;
}
// Helper method to print a linked list
private void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
MergeKSortedLists solution = new MergeKSortedLists();
// Example 1
int[][] arrays1 = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
ListNode[] lists1 = solution.arraysToLinkedLists(arrays1);
ListNode mergedList1 = solution.mergeKLists(lists1);
solution.printList(mergedList1);
// Example 2
int[][] arrays2 = {};
ListNode[] lists2 = solution.arraysToLinkedLists(arrays2);
ListNode mergedList2 = solution.mergeKLists(lists2);
solution.printList(mergedList2);
// Example 3
int[][] arrays3 = {{}};
ListNode[] lists3 = solution.arraysToLinkedLists(arrays3);
ListNode mergedList3 = solution.mergeKLists(lists3);
solution.printList(mergedList3);
}
}
This Java code defines a MergeKSortedLists class with a mergeKLists method to merge k sorted linked lists. The ListNode class is used to represent a node in the linked list. The arraysToLinkedLists, arrayToLinkedList, and printList methods are helper methods for data conversion and printing. The main method demonstrates the usage with the provided examples.
Python Solution
Here’s the equivalent Python code for merging k sorted linked lists using a min heap:
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
if not lists:
return None
# Use a min heap to keep track of the smallest element at the front
min_heap = []
# Add the head of each list to the min heap
for node in lists:
if node:
heapq.heappush(min_heap, (node.val, node))
dummy = ListNode(0)
current = dummy
# Keep popping the smallest element from the min heap and add its next to the heap
while min_heap:
val, node = heapq.heappop(min_heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(min_heap, (node.next.val, node.next))
return dummy.next
# Helper function to convert an array to a linked list
def array_to_linked_list(array):
dummy = ListNode(0)
current = dummy
for value in array:
current.next = ListNode(value)
current = current.next
return dummy.next
# Helper function to print a linked list
def print_list(head):
while head:
print(head.val, end=" ")
head = head.next
print()
# Example 1
arrays1 = [[1, 4, 5], [1, 3, 4], [2, 6]]
lists1 = [array_to_linked_list(array) for array in arrays1]
merged_list1 = merge_k_lists(lists1)
print_list(merged_list1)
# Example 2
arrays2 = []
lists2 = [array_to_linked_list(array) for array in arrays2]
merged_list2 = merge_k_lists(lists2)
print_list(merged_list2)
# Example 3
arrays3 = [[]]
lists3 = [array_to_linked_list(array) for array in arrays3]
merged_list3 = merge_k_lists(lists3)
print_list(merged_list3)
This Python code uses the heapq module to implement a min heap for efficiently merging k sorted linked lists. The merge_k_lists function takes a list of linked lists as input and returns the merged sorted linked list. The ListNode class is used to represent a node in the linked list. The array_to_linked_list, print_list, and examples demonstrate the usage of the function with the provided test cases.