Q7 Merge K sorted linked lists | Practice | GeeksforGeeks

//{ Driver Code Starts
import java.util.*;

class Node
{
    int data;
    Node next;
    
    Node(int key)
    {
        data = key;
        next = null;
    }
}


class GfG
{
    public static void printList(Node node)
    {
        while(node != null)
        {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-- > 0)
        {   
            int N = sc.nextInt();
            
            Node []a = new Node[N];
            
            for(int i = 0; i < N; i++)
            {
                int n = sc.nextInt();
                
                Node head = new Node(sc.nextInt());
                Node tail = head;
                
                for(int j=0; j<n-1; j++)
                {
                    tail.next = new Node(sc.nextInt());
                    tail = tail.next;
                }
                
                a[i] = head;
            }
            
            Solution g = new Solution();
             
            Node res = g.mergeKList(a,N);
            if(res!=null)
                printList(res);
            System.out.println();
        }
    }
}
// } Driver Code Ends


/*class Node
{
    int data;
    Node next;
    
    Node(int key)
    {
        data = key;
        next = null;
    }
}
*/

// a is an array of Nodes of the heads of linked lists
// and N is size of array a


class Solution
{
    //Function to merge K sorted linked list.
     //Function to merge two sorted linked list.
    Node mergeTwoLists(Node head1, Node head2) {
     Node dummy = new Node(-1);
     Node c1 = head1;
     Node c2 = head2;
     
     while(c1 != null && c2 != null){
         
         if(c1.data <= c2.data){
             dummy.next = c1;
             c1 = c1.next;
             dummy = dummy.next;
         }
         else{
             dummy.next = c2;
             c2 = c2.next;
             dummy = dummy.next;
         }
     }
     //attach the rest of the list which ever is not empty
     dummy.next =  c1 == null ? c2 :c1;
     
     return head1.data <= head2.data ? head1 : head2;
   } 
   Node mergeKList_helper(Node[]arr,int si , int ei){  //si , ei are starting and ending index
       //base condition
       if(si == ei )
       return arr[si];
       
       int mid = (si + ei)/2;
       Node l1 = mergeKList_helper(arr,si,mid);
       Node l2 = mergeKList_helper(arr,mid+1,ei);
       
       return mergeTwoLists(l1 , l2);
   }
   
   
    Node mergeKList(Node[]arr,int K)
    {
        if(arr.length == 0 )
        return null;
        
        return  mergeKList_helper(arr , 0 , arr.length -1);
        
    }
}