Merge k Sorted Lists

Problem Statement

In this challenge, you are provided with an array of k linked-lists named lists, where each element in lists is a singly-linked list that is already sorted in ascending order. Your task is to merge all these linked-lists into a single linked-list which is also sorted in ascending order. Ultimately, you should return this merged and sorted linked-list. Consider not only merging the values but the entire nodes of the linked lists.

Examples

Example 1

Input:

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

Output:

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

Explanation:

The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2

Input:

lists = []

Output:

[]

Example 3

Input:

lists = [[]]

Output:

[]

Constraints

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

Approach and Intuition

Overview

The problem essentially asks for a way to integrate multiple sorted sequences into a single sorted sequence. This merging operation is a common task in algorithms involving sorted data, such as the merge step in merge sort.

Step-by-Step Process

1. Initialization: First, a priority queue (min-heap) can be initialized to help in sorting the elements from all linked-lists in real-time.

2. Heap Population: Insert the first node of each linked-list into the priority queue. Since these lists are sorted, initially, we only need the first element of each list to determine the smallest element.

3. Merging Mechanism:

   • Extract the smallest element node from the heap.
   • Append the extracted node to the result linked-list.
   • Insert the next node of the extracted node's linked-list into the heap.
   • Continue this process until the heap is empty.

Example Walkthrough

• For Example 1, the process would involve:

  • Adding the heads of all three lists 1, 1, and 2 into the heap.
  • Repeatedly: remove the smallest element from the heap, add it to the result linked-list, and add the next node of the extracted node's list to the heap.
  • This would result in the merged list [1, 1, 2, 3, 4, 4, 5, 6].

• For Example 2, with an empty list of lists, the resulting linked-list is also empty because there are no nodes to merge.

• In Example 3, where the list contains an empty list, the result remains an empty linked-list as there are no elements to process.

Consideration of Constraints

• The memory efficiency hinges on keeping only k nodes in the heap at any given time, where k is the number of linked-lists.
• The method ensures that we utilize the given fact that each individual linked-list is sorted, which simplifies our merging process since we initially consider only the first node of each linked-list.

Solutions

// Definition for singly-linked list.
// struct ListNode {
//    int value;
//    ListNode *nextNode;
//    ListNode(int x) : value(x), nextNode(nullptr) {}
//};
class Solution {
public:
    ListNode* combineLists(vector<ListNode*>& multiLists) {
        vector<int> values;
        ListNode root(0);
        ListNode* current = &root;
        for (ListNode* eachList : multiLists) {
            while (eachList) {
                values.push_back(eachList->value);
                eachList = eachList->nextNode;
            }
        }
        sort(values.begin(), values.end());
        for (int val : values) {
            current->nextNode = new ListNode(val);
            current = current->nextNode;
        }
        return root.nextNode;
    }
};