//{ 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); } }