Merge K Sorted Lists

Flatten every list into one big array of values, sort it, then rebuild a linked list from the sorted array. Here N is the total number of nodes across all lists. This ignores the fact that each individual list already arrives pre-sorted — real information that a smarter approach can exploit.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(self, lists: list[ListNode | None]) -> ListNode | None:
        values = []
        for node in lists:
            while node:
                values.append(node.val)
                node = node.next
        values.sort()

        dummy = ListNode()
        tail = dummy
        for v in values:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

Correct, but sorting from scratch costs O(N log N) and throws away the pre-sorted structure of the input lists — both smarter approaches below merge in O(N log k) instead by only ever comparing current list heads against each other.

Keep a min-heap containing the current head of each of the k lists. Repeatedly pop the smallest head, append it to the result, and push its next node (if any) back onto the heap. The heap always holds at most k elements, so each pop/push is O(log k) instead of the O(k) a linear scan across k heads would cost.

import heapq

class Solution:
    def mergeKLists(self, lists: list[ListNode | None]) -> ListNode | None:
        heap = []
        for i, node in enumerate(lists):
            if node:
                # include the list index as a tiebreaker so ListNode objects
                # (which are not comparable) never need to be compared directly
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode()
        tail = dummy
        while heap:
            val, i, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

Tracing lists = [[1,4,5],[1,3,4],[2,6]] — watch the heap hold exactly one head per list, surface the smallest, and pop it into the merged chain (trace data lives in this problem folder’s data.ts, replayed by the same loop as the code):

Why it’s correct: at every step, the heap’s minimum is the smallest value not yet placed in the output, because it holds exactly the current “frontier” (one candidate per list) — the same invariant as the two-list merge, generalized to k candidates. Complexity: every one of the N nodes is pushed and popped exactly once, each operation costing O(log k) on a heap of size at most k → O(N log k) time, O(k) space for the heap.

Pair up the lists and merge each pair with the ordinary two-list merge, halving the number of lists. Repeat until only one list remains — like the merge step of merge sort, but merging whole lists instead of splitting one. This reaches the same O(N log k) time as the heap approach without needing any auxiliary heap storage, since it reuses the existing nodes and only a small number of pointer variables.

class Solution:
    def mergeKLists(self, lists: list[ListNode | None]) -> ListNode | None:
        if not lists:
            return None
        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(self._merge_two(l1, l2))
            lists = merged
        return lists[0]

    def _merge_two(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Tracing lists = [[1,4,5],[1,3,4],[2,6]]: round 1 merges list [1,4,5] with [1,3,4] into [1,1,3,4,4,5], and [2,6] is left unpaired, passing through unchanged; round 2 merges [1,1,3,4,4,5] with [2,6] into the final [1,1,2,3,4,4,5,6].

Why it’s correct: each round preserves sortedness (every merge is the already-proven-correct two-list merge), and pairing lists up halves the count each round, so after ⌈log₂ k⌉ rounds exactly one fully-merged list remains. Complexity: across all rounds, every node participates in exactly one merge per round, and there are O(log k) rounds → O(N log k) time; only pointer variables and a merged list of list-heads are allocated, no per-node auxiliary structure → O(1) extra space beyond the output pointers — this matches the heap approach’s time complexity with a smaller constant-factor memory footprint, making it the preferred answer in practice.