Merge K sorted linked list

Merge K Sorted Linked List 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.

Approaches

1. Brute force : add all the elements of linked list in an array and sort them, link them and give the output

2. Merge list one by one : merge 2 list and then merge the 3 one to it Space o(n) , iterations n because all the lists needs to be iterated n times

3. use a priority queue, add only the first elements of the list of list to the queue and poll one by one, smallest ia always the first

private Node mergeKSortedListPriorityQueue(List<Node> inputList, Node finalList) {

       /**
        * Priority queue quick reveison
        * Priority queue is based on natural order sorting of elements
        * Priority queue is not thread safe
        * Prioity queue is non blocking , unbounded
        * Bounded blocking queue is Blocking queue impl of priority queue
        * 
        * 
        * Time complexity : O(Nlogk) where k is the number of linked lists.
        * There are N nodes in the final linked list.
        * O(logk) compaisions because we are ideally comparing only a few elements at any given point of time
        * Cost of comparision : O(1)
        * Space complexity : o(n)
        */
       Node preHead = finalList;

       PriorityQueue<Node> priorityQ = new PriorityQueue<>(new Comparator<Node>() {
           public int compare(Node o1, Node o2) {
               if (o1.val > o2.val) {
                   return 1;
               } else if (o1.val == o2.val) {
                   return 0;
               } else {
                   return -1;
               }
           };
       });

       for (Node node : inputList) {
           while(node != null) {
               priorityQ.add(node);   //added only the head pointers of the 3 nodes
           }
       } 
       
       //remove nodes from priority queue, smallest is at the top always
       while (!priorityQ.isEmpty()) {
           Node polledNode = priorityQ.poll();
           preHead = polledNode;
           preHead = preHead.next;
           if(polledNode.next != null) {
               priorityQ.add(polledNode.next); //keep adding only the next element from each list
               polledNode = polledNode.next;
           }
       }
       return finalList;
    }