Merge K Sorted Linked List Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/merge-k-sorted-linked-lists/1

(It is also the problem of the day for 07-03-2022)

Solution:

class Solution

{

    //Function to merge K sorted linked list.

    Node mergeKList(Node[]arr,int K)

    {

        PriorityQueue<Integer>pq=new PriorityQueue<Integer>();

        for(int i=0;i<arr.length;i++){

            Node temp=arr[i];

            while(temp!=null){

                pq.add(temp.data);

                temp=temp.next;

            }

        }

        //System.out.println(pq);

        

    

     Node obj=new Node(0);

     Node temp=obj;

     while(!pq.isEmpty()){

         temp.next=new Node(pq.remove());

         temp=temp.next;

     }

     temp.next=null;

     return obj.next;

     

    }

}

(Number of linked list given==array size==k)

Time Complexity: O(number of the linked lists given *Size of each linked list)[GFG Time:3.9/5.7]

Space Complexity: O(number of linked lists given * size of each linked list)

Auxiliary Space: O(k)[Priority Queue will be used of size equal to the sum of the size of all given linked lists.]

Approach Used:

Here we will traverse the array of linked lists and store the value of each node data into the priority queue.

Later we will make a new linked list named obj and store all the data values from the priority queue into the obj linked list.

Here we created obj as a new linked list and also created a pointer temp pointing to the head of obj ArrayList.

obj=0

temp->obj

Now we will traver till pq is empty and everytme create new node and store the value of data fro linked list and append the newly created nodes in obj linked list.

as while(!pq.isEmpty()){

    temp.next=new Node(pq.remove());//temp was earlier pointing to head so by temp.next a new node will be created and have data value as pq.emove()

    temp=temp.next;// after the new node creation we move further so by temp.next we will move to new node.

}

temp.next=null;//By this line we made the reference of the last node as null which also means no reference will be stored in this list.

return obj//this will return the head or base address of the linked list.

Total Test Cases:255

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"