Untitled
unknown
plain_text
10 months ago
2.5 kB
3
Indexable
import java.util.*; class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class MergeKSortedLists { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.val)); // Add all the heads of the lists to the priority queue for (ListNode node : lists) { if (node != null) { pq.add(node); } } ListNode dummy = new ListNode(0); ListNode tail = dummy; while (!pq.isEmpty()) { // Remove the smallest node from the priority queue ListNode smallest = pq.poll(); tail.next = smallest; tail = smallest; // Move tail to the inserted node // Add the next node of the extracted node to the priority queue if (smallest.next != null) { pq.add(smallest.next); } } return dummy.next; } // Helper method to create a linked list from array public ListNode createList(int[] array) { if (array == null || array.length == 0) { return null; } 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 the linked list public void printList(ListNode head) { ListNode current = head; while (current != null) { System.out.print(current.val + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { MergeKSortedLists solution = new MergeKSortedLists(); // Example input as arrays int[] arr1 = {1, 4, 5}; int[] arr2 = {1, 3, 4}; int[] arr3 = {2, 6}; // Create linked lists from arrays ListNode l1 = solution.createList(arr1); ListNode l2 = solution.createList(arr2); ListNode l3 = solution.createList(arr3); // Merge k sorted lists ListNode[] lists = {l1, l2, l3}; ListNode mergedList = solution.mergeKLists(lists); // Print the merged list solution.printList(mergedList); } }
Editor is loading...
Leave a Comment