Merge K Sorted Linked Lists

Problem

You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Examples

Example 1:

Input: lists = [[1,2,4],[1,3,5],[3,6]]

Output: [1,1,2,3,3,4,5,6]

Example 2:

Input: lists = []

Output: []

Example 3:

Input: lists = [[]]

Output: []

Constraints

• 0 <= lists.length <= 1000
• 0 <= lists[i].length <= 100
• -1000 <= lists[i][j] <= 1000

You should aim for a solution as good or better than O(n * k) time and O(1) space, where k is the total number of lists and n is the total number of nodes across all lists.

Solution

Have vector of head of each linked list. At every loop iteration, find minimum value head, assign to the current list, increment the selected head, then remove empty lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode head{0};
 
        // Remove min elements
        std::erase_if(lists, [](ListNode* n){
            return n == nullptr;
        });
 
        ListNode *current = &head;
        while (!lists.empty()) {
            ListNode **min_head = nullptr;
            int min_val = std::numeric_limits<int>::max();
            // Find min head
            for (auto &l : lists) {
                if (l->val < min_val) {
                    min_val = l->val;
                    min_head = &l;
                }
            }
            // Assign to next and increment
            current->next = *min_head;
            current = current->next;
            *min_head = (*min_head)->next;
            
            // Remove min elements
            std::erase_if(lists, [](ListNode* n){
                return n == nullptr;
            });
        }
        return head.next;
    }
};