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

To merge k sorted linked lists, one approach is to repeatedly merge two of the linked lists until all k lists have been merged into one. We can use a priority queue to keep track of the minimum element across all k linked lists at any given time.

Here's the code to implement this idea:

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Custom comparator for the priority queue
struct CompareNode {
    bool operator()(const ListNode* node1, const ListNode* node2) const {
        return node1->val > node2->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq;
    for (ListNode* list : lists) {
        if (list) {
            pq.push(list);
        }
    }
    ListNode* dummy = new ListNode(-1);
    ListNode* curr = dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();
        curr->next = node;
        curr = curr->next;
        if (node->next) {
            pq.push(node->next);
        }
    }
    return dummy->next;
}

We start by initializing a priority queue with all the head nodes of the k linked lists. We use a custom comparator that compares the values of two nodes and returns true if the first node's value is less than the second node's value.

We then create a dummy node to serve as the head of the merged linked list, and a current node to keep track of the last node in the merged linked list. We repeatedly pop the minimum node from the priority queue and append it to the merged linked list. If the popped node has a next node, we push it onto the priority queue. Once the priority queue is empty, we return the head of the merged linked list.

Note that this implementation has a time complexity of O(n log k), where n is the total number of nodes across all k linked lists, and a space complexity of O(k).