Merge K Sorted 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) {
        if (lists.empty()) return nullptr;
        
        auto cmp = [](ListNode* a, ListNode* b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        
        for (auto list : lists) {
            if (list) pq.push(list);
        }
        
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            tail->next = node;
            tail = tail->next;
            if (node->next) pq.push(node->next);
        }
        
        return dummy.next;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            current.next = node;
            current = current.next;
            
            if (node.next != null) {
                pq.offer(node.next);
            }
        }
        
        return dummy.next;
    }
}

                                            
import heapq

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for idx, node in enumerate(lists):
            if node:
                heap.append((node.val, idx, node))
        heapq.heapify(heap)
        
        dummy = ListNode()
        curr = dummy
        
        while heap:
            val, idx, node = heapq.heappop(heap)
            curr.next = ListNode(val)
            curr = curr.next
            if node.next:
                heapq.heappush(heap, (node.next.val, idx, node.next))
        
        return dummy.next

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists == null || lists.Length == 0) return null;
        
        ListNode result = null;
        foreach (var list in lists)
        {
            result = MergeTwoLists(result, list);
        }
        
        return result;
    }
    
    private ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val < l2.val)
        {
            l1.next = MergeTwoLists(l1.next, l2);
            return l1;
        }
        else
        {
            l2.next = MergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const mergeTwoLists = (l1, l2) => {
        if (!l1) return l2;
        if (!l2) return l1;
        
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    
    const merge = (lists, start, end) => {
        if (start === end) return lists[start];
        if (start > end) return null;
        
        const mid = Math.floor((start + end) / 2);
        const left = merge(lists, start, mid);
        const right = merge(lists, mid + 1, end);
        
        return mergeTwoLists(left, right);
    }
    
    return merge(lists, 0, lists.length - 1);
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if (lists.length === 0) return null;

    const mergeTwoLists = (l1: ListNode | null, l2: ListNode | null): ListNode | null => {
        if (!l1) return l2;
        if (!l2) return l1;

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    };

    const merge = (left: number, right: number): ListNode | null => {
        if (left === right) return lists[left];
        const mid = Math.floor((left + right) / 2);
        const l1 = merge(left, mid);
        const l2 = merge(mid + 1, right);
        return mergeTwoLists(l1, l2);
    };

    return merge(0, lists.length - 1);
};

                                            
class Solution {
    /**
     * @param ListNode[] $lists
     * @return ListNode
     */
    function mergeKLists($lists) {
        $arr = [];
        foreach ($lists as $list) {
            while ($list != null) {
                $arr[] = $list->val;
                $list = $list->next;
            }
        }
        sort($arr);
        
        $dummy = new ListNode(0);
        $cur = $dummy;
        foreach ($arr as $val) {
            $cur->next = new ListNode($val);
            $cur = $cur->next;
        }
        
        return $dummy->next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        var values = [Int]()
        
        for list in lists {
            var current = list
            while current != nil {
                values.append(current!.val)
                current = current?.next
            }
        }
        
        values.sort()
        
        var newHead: ListNode?
        var current: ListNode?
        
        for value in values {
            if newHead == nil {
                newHead = ListNode(value)
                current = newHead
            } else {
                current?.next = ListNode(value)
                current = current?.next
            }
        }
        
        return newHead
    }
}

                                            
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeKLists(lists: Array<ListNode?>): ListNode? {
        if (lists.isEmpty()) return null
        return merge(lists, 0, lists.size - 1)
    }
    
    fun merge(lists: Array<ListNode?>, left: Int, right: Int): ListNode? {
        if (left == right) return lists[left]
        
        val mid = left + (right - left) / 2
        val l1 = merge(lists, left, mid)
        val l2 = merge(lists, mid + 1, right)
        
        return mergeTwoLists(l1, l2)
    }
    
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        if (l1 == null) return l2
        if (l2 == null) return l1
        
        if (l1.`val` < l2.`val`) {
            l1.next = mergeTwoLists(l1.next, l2)
            return l1
        } else {
            l2.next = mergeTwoLists(l1, l2.next)
            return l2
        }
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  ListNode? mergeKLists(List<ListNode?> lists) {
    List<int> allNodes = [];
    for (var listNode in lists) {
      while (listNode != null) {
        allNodes.add(listNode.val);
        listNode = listNode.next;
      }
    }
    allNodes.sort();
    ListNode dummy = ListNode();
    ListNode current = dummy;
    for (int nodeVal in allNodes) {
      current.next = ListNode(nodeVal);
      current = current.next!;
    }
    return dummy.next;
  }
}

                                            
%% Definition for singly-linked list.
%%
%% -record(list_node, {val = 0 :: integer(),
%%                     next = null :: 'null' | #list_node{}}).
-spec merge_k_lists(Lists :: [#list_node{} | null]) -> #list_node{} | 
null.
merge_k_lists(Lists) ->
    merge(Lists).

merge([H|T]) ->
    merge_two_lists(H, merge(T));
merge([]) ->
    null.

merge_two_lists(null, L) ->
    L;
merge_two_lists(L, null) ->
    L;
merge_two_lists(L1 = #list_node{val = Val1, next = Next1}, L2 = #list_node{val = Val2, next = Next2}) when Val1 < Val2 ->
    L1#list_node{next = merge_two_lists(Next1, L2)};
merge_two_lists(L1, L2) ->
    L2#list_node{next = merge_two_lists(L1, L2#list_node.next)}.

To solve this coding challenge, we need to merge multiple sorted linked lists into one single sorted linked list. This is a typical problem that can be efficiently addressed using a min-heap (or priority queue). The main idea is to take advantage of the inherently sorted nature of the lists and the efficient access to the minimum element provided by the min-heap to construct the resulting list in a sorted manner.

# Explanation

We can break down our approach into clear steps:

Initialization : We will start by initializing a min-heap. Each element in the heap will be a tuple containing the value of a node, the index of the list the node comes from, and the node itself. This will help us keep track of the nodes and their origins.
Heap Population : Iterate over all the linked lists and push the first node (if it exists) of each list into the heap.
Building the Result : Use a dummy node to facilitate the construction of the result linked list. As long as the heap is not empty:

Extract the smallest node from the heap (this will be the node with the smallest value among the current heads of the lists).
Append this node to the result list.
If the extracted node has a next node in its original list, push this next node into the heap.

Return the Result : The next node of the dummy node will be the head of the merged sorted linked list.

# Detailed Steps in Pseudocode

Initialize a min-heap and a dummy node :

                                            
# Create a min-heap to store nodes
minHeap = initialize an empty heap

# Create a dummy node and a current pointer for result linked list
dummyNode = new ListNode(0)
current = dummyNode

Populating the heap with the first node of each list :

                                            
# Iterate over each linked list
for each list in lists:
# If the list is not empty, push the first node into the heap
if list is not None:
minHeap.push((list's first node value, list index, list's first node))

Building the result linked list :

                                            
# While there are elements in the heap
while minHeap is not empty:
# Extract the node with the smallest value
smallestNodeValue, listIndex, smallestNode = minHeap.pop()

# Append this smallest node to the result list
current.next = new ListNode(smallestNodeValue)
current = current.next

# If there is a next node in the same list, push it into the heap
if smallestNode.next is not None:
minHeap.push((smallestNode.next.value, listIndex, smallestNode.next))

Return the head of the merged list :

                                            
# The head of the merged list is the next of dummyNode
return dummyNode.next

With these detailed steps, the challenge of merging k sorted linked lists is transformed into an organized series of operations focused on the properties of heaps and linked lists. This approach ensures that the final merged list is built in a time-efficient manner, leveraging the min-heap to always access the smallest available node among the heads of the lists. This method, which effectively uses a priority queue (min-heap), results in a time complexity of O(N log k), where N is the total number of nodes across all lists and k is the number of lists. This makes it an efficient approach for large inputs as specified in the problem constraints.