Merge K Sorted Linkedlist Algorithm

The Merge K Sorted Linkedlists Algorithm is an efficient technique used to combine multiple sorted linked lists into a single, sorted linked list. This algorithm is particularly useful in scenarios where a large data set is divided into smaller, sorted linked lists, and the goal is to merge them together while maintaining the sorted order. The basic idea behind the algorithm is to compare the smallest (or largest, depending on the sort order) elements from each of the individual linked lists, and then merge them together to form a new, sorted linked list. This process is repeated until all the elements from the given linked lists are included in the final, merged linked list. There are several approaches to implement the Merge K Sorted Linkedlists Algorithm, one of which is the divide and conquer method. In this approach, the problem of merging K sorted linked lists is divided into smaller subproblems, where pairs of linked lists are merged together using a standard two-pointer merge algorithm for sorted linked lists. This process is carried out in a hierarchical manner, with the results from the lower levels being combined and merged at higher levels, until a single, sorted linked list is obtained. Another approach is to use a min-heap or priority queue, which stores the smallest (or largest) element from each individual linked list. The algorithm then extracts the minimum (or maximum) element from the heap, appends it to the merged linked list, and inserts the next element from the same linked list into the heap. This process continues until all the elements are processed, resulting in a single, sorted linked list. Overall, the Merge K Sorted Linkedlists Algorithm is an effective and versatile method for combining multiple sorted linked lists into a single sorted list.
package DataStructures.Lists;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Arun Pandey (https://github.com/pandeyarun709)
 */
public class Merge_K_SortedLinkedlist {

    /**
     * This function merge K sorted LinkedList
     *
     * @param a array of LinkedList
     * @param N size of array
     * @return node
     */
    Node mergeKList(Node[] a, int N) {
        // Min Heap
        PriorityQueue<Node> min = new PriorityQueue<>(Comparator.comparingInt(x -> x.data));

        // adding head of all linkedList in min heap
        min.addAll(Arrays.asList(a).subList(0, N));

        // Make new head among smallest heads in K linkedList 
        Node head = min.poll();
        min.add(head.next);
        Node curr = head;

        // merging LinkedList
        while (!min.isEmpty()) {

            Node temp = min.poll();
            curr.next = temp;
            curr = temp;

            // Add Node in min Heap only if temp.next is not null
            if (temp.next != null) {
                min.add(temp.next);
            }
        }

        return head;
    }

    private class Node {
        private int data;
        private Node next;

        public Node(int d) {
            this.data = d;
            next = null;
        }
    }
}

LANGUAGE:

DARK MODE: