Given K sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list.

The task is to merge them in such a way that after merging they will be a single sorted linked list.

Given K sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list.

The task is to complete the function mergeKList() which merges the K given lists into a sorted one. The printing is done automatically by the driver code.

Expected Time Complexity: O(nkLogk)
Expected Auxiliary Space: O(k)

Input:
2
4
3 1 2 5 2 7 8 2 10 11 2 14 15
3
2 1 3 3 4 5 6 1 8
Output:
1 2 5  7 8 10 11 14 15
1 3 4 5 6 8

Explanation :
Testcase 1: The test case has 4 sorted linked list of size 3, 2, 2, 2
1st    list     1 -> 2-> 5
2nd   list      7->8
3rd    list      10->11
4th    list      14->15
The merged list will be 1->2->5->7->8->10->11->14->15
Testcase 2: The test case has 3 sorted linked list of size 2, 3, 1.
1st list 1 -> 3
2nd list 4 -> 5 -> 6
3rd list 8
The merged list will be 1->3->4->5->6->8.

// { Driver Code Starts
// C++ program to merge k sorted arrays of size n each
#include <bits/stdc++.h>

using namespace std;

// A Linked List node
struct Node {
    int data;
    Node * next;

    Node(int x) {
        data = x;
        next = NULL;
    }

};

Node * mergeKLists(Node * arr[], int N);

/* Function to print nodes in a given linked list */
void printList(Node * node) {
    while (node != NULL) {
        printf("%d ", node - > data);
        node = node - > next;
    }
    cout << endl;
}

// Driver program to test above functions
int main() {
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        struct Node * arr[N];
        for (int j = 0; j < N; j++) {
            int n;
            cin >> n;

            int x;
            cin >> x;
            arr[j] = new Node(x);
            Node * curr = arr[j];
            n--;

            for (int i = 0; i < n; i++) {
                cin >> x;
                Node * temp = new Node(x);
                curr - > next = temp;
                curr = temp;
            }
        }

        Node * res = mergeKLists(arr, N);
        printList(res);

    }

    return 0;
}
// } Driver Code Ends


/*Linked list Node structure

struct Node
{
  int data;
  Node* next;
  
  Node(int x){
      data = x;
      next = NULL;
  }
  
};
*/

/* arr[] is an array of pointers to heads of linked lists
  and N is size of arr[]  */
bool sot(Node * a, Node * b) {
    if (a - > data < b - > data)
        return 1;
    else
        return 0;
}
Node * mergeKLists(Node * arr[], int N) {
    // Your code herei
    int i = 0;
    vector < Node * > v;
    while (i < N) {
        int j = arr[i] - > data;
        Node * p = arr[i], * q = NULL;
        while (p != NULL) {
            q = p;
            p = q - > next;
            v.push_back(q);
        }
        ++i;

    }
    sort(v.begin(), v.end(), sot);
    Node * head = NULL;
    head = v[0];
    for (int i = 0; i < v.size() - 1; ++i) {
        v[i] - > next = v[i + 1];
    }
    return head;
}