Assumptions:- ListNode values are integers (could be negative), fit in Python int.- Total number of nodes across all lists = N. Number of lists = k. k can be up to N (many small lists) or 1.- Lists are singly-linked, already sorted ascending, may be empty or None.Brute-force approach:- Concatenate all nodes/values into an array, sort it, then build a linked list.- Time: O(N log N), Space: O(N). Simple but not optimal when k is small relative to N.Heap-based optimization (recommended):- Use a min-heap of size up to k storing (node.val, unique_id, node) to avoid tie issues.- Initialize heap with head of each non-empty list.- Repeatedly pop smallest node, append to result, and if popped node has next, push next to heap.- Time: O(N log k) (each node pushed/popped once, heap ops cost log k). Space: O(k) for heap plus O(1) extra for pointers (result uses existing nodes).Implementation with narration of edge cases and tests while coding:- Handle k == 0 or all lists None -> return None.- Handle duplicates and negative values (heap comparator handles ties via unique_id).- Test cases to run: empty input, single list, multiple lists with varying lengths, all lists empty, lists with duplicate values.Python implementation:python
import heapq
from typing import List, Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return f"{self.val}->" + (repr(self.next) if self.next else "None")
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
"""
Merge k sorted linked lists using a min-heap.
Time: O(N log k), Space: O(k)
"""
heap = []
counter = 0 # unique tie-breaker
# Edge case: empty input
if not lists:
return None
# Initialize heap with non-empty heads
for node in lists:
if node:
heapq.heappush(heap, (node.val, counter, node))
counter += 1
# Dummy head for result list
dummy = ListNode(0)
tail = dummy
while heap:
val, _, node = heapq.heappop(heap)
# Append existing node to result (reusing nodes)
tail.next = node
tail = tail.next
# If there's a next node, push it into heap
if node.next:
heapq.heappush(heap, (node.next.val, counter, node.next))
counter += 1
# Ensure tail.next is None in case reused nodes had next pointers lingering
tail.next = None
return dummy.next
