package com.thealgorithms.datastructures.lists;

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

/**
 * The MergeKSortedLinkedList class provides a method to merge multiple sorted linked lists
 * into a single sorted linked list.
 * This implementation uses a min-heap (priority queue) to efficiently
 * find the smallest node across all lists, thus optimizing the merge process.
 *
 * <p>Example usage:
 * <pre>
 * Node list1 = new Node(1, new Node(4, new Node(5)));
 * Node list2 = new Node(1, new Node(3, new Node(4)));
 * Node list3 = new Node(2, new Node(6));
 * Node[] lists = { list1, list2, list3 };
 *
 * MergeKSortedLinkedList merger = new MergeKSortedLinkedList();
 * Node mergedHead = merger.mergeKList(lists, lists.length);
 * </pre>
 * </p>
 *
 * <p>This class is designed to handle nodes of integer linked lists and can be expanded for additional data types if needed.</p>
 *
 * @author Arun Pandey (https://github.com/pandeyarun709)
 */
public class MergeKSortedLinkedList {

    /**
     * Merges K sorted linked lists into a single sorted linked list.
     *
     * <p>This method uses a priority queue (min-heap) to repeatedly extract the smallest node from the heads of all the lists,
     * then inserts the next node from that list into the heap. The process continues until all nodes have been processed,
     * resulting in a fully merged and sorted linked list.</p>
     *
     * @param a Array of linked list heads to be merged.
     * @param n Number of linked lists.
     * @return Head of the merged sorted linked list.
     */
    Node mergeKList(Node[] a, int n) {
        if (a == null || n == 0) {
            return null;
        }

        // Min Heap to store nodes based on their values for efficient retrieval of the smallest element.
        PriorityQueue<Node> minHeap = new PriorityQueue<>(Comparator.comparingInt(x -> x.data));

        // Initialize the min-heap with the head of each non-null linked list
        for (Node node : a) {
            if (node != null) {
                minHeap.add(node);
            }
        }

        // Start merging process
        Node head = minHeap.poll(); // Smallest head is the initial head of the merged list
        if (head != null && head.next != null) {
            minHeap.add(head.next);
        }

        Node curr = head;
        while (!minHeap.isEmpty()) {
            Node temp = minHeap.poll();
            curr.next = temp;
            curr = temp;

            // Add the next node in the current list to the heap if it exists
            if (temp.next != null) {
                minHeap.add(temp.next);
            }
        }

        return head;
    }

    /**
     * Represents a node in the linked list.
     */
    static class Node {
        int data;
        Node next;

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

        Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}