We want to leverage the fact that the k-lists are sorted so we avoid doing the extra work to find the minimum that would otherwise lead to a n * k solution.

The key idea is that we do not progress to a next node until we know that out of all current nodes in consideration, no node is the minimum node. Given this, we know that at any given time we will be considering k nodes, and that a heap structure can allow us to reach optimality by adding the nodes directly in an ordered heap to construct the ordered linked list.

1. Initialise a min-heap with the first node from each non-empty list

2. Use a counter as a tiebreaker in the heap to handle duplicate values (Python can't compare ListNode objects directly)

3. Create a dummy node to simplify linked list construction

4. While the heap isn't empty:

- Pop the minimum node from the heap

- Attach it to our result list

- If this node has a next node, push it into the heap

5. Return the merged list (dummy.next)

Time complexity: O(nlogk)

We process n total nodes

Each heap operation (push/pop) takes O(log k) time

Total: n operations × O(log k) = O(n log k)

Space complexity: O(k)

The heap stores at most k nodes at any time (one candidate from each list)

We reuse existing ListNode objects rather than creating new ones

class Solution:

def mergekLists(self, lists: List[Optional[ListNode]]) → Optional [ListNode]:

  all_elements: list[int] = 1]

for head in lists:

while head:

      all_elements. append (head. val)

      head = head.next

if not all_elements:

    return None

  all_elements.sort ()

  dummy = ListNode(0)

  current_node = dummy

  for element in all_elements:

  current_node. next = ListNode(element)

current_node = current_node.next

return dummy.next

from math import inf

class Solution:

    def mergeKLists(self, lists: List[Optional[ListNode]]) → Optional[ListNode]:

        k_lists: list = []

        for head in lists:

            k_lists.append(head)

        len_k_lists: len(k_lists)

        final_elements: list[int] = []

        while k_lists: # step (considering k-heads)

            len_k_lists = len(k_lists)

            for i in range(len_k_lists):

                if k_lists[i].val < current_minimum:

                    current_minimum = k_lists[i].val

                if k_lists[i].val == current_minimum:

                    final_elements.append(current_minimum)

        current_node = dummy

        for element in final_elements:

            current_node.next = ListNode(element)

            current_node = current_node.next

        return dummy.next

import heapq

class Solution:

    def mergeKLists(self, lists: List[Optional[ListNode]]) → Optional[ListNode]:

        k_lists: list = []

        counter: int = 0

        for head in lists:

            if head:

                heapq.heappush(k_lists, (head.val, counter, head))

                counter += 1

        len_k_lists: len(k_lists)

        dummy = ListNode(0)

        current_node = dummy

        while k_lists: # step (considering k-heads)

            next_min_value, counter, head = heapq.heappop(k_lists)

            current_node.next = head

            current_node = current_node.next

            if head.next:

                heapq.heappush(k_lists, (head.next.val, counter, head.next))

                counter += 1

        return dummy.next