💬 Discord
Sign In
NeetCode #341LC-23HardLinked ListBlind 75NC 150NC 250
← Back to All Problems

#341 · #23 · Merge k Sorted Lists(合并 K 个升序链表)

📌 Problem Statement & Constraints

You are given an array of k sorted linked lists. Merge them into one sorted list and return its head. Constraints: k is in [0, 10^4], the total number of nodes is at most 10^4.

💡 Core Algorithmic Approaches

  1. Put the head of each non-empty list into a min-heap keyed by value.
  2. Repeatedly pop the smallest node, append it to the result, and push its successor.
  3. Important: heap entries must be comparable, and ListNode objects are not, so include a tie-breaker such as the list index in the tuple.
  4. This is O(N log k) where N is the total number of nodes, versus O(N log N) for the concatenate-and-sort approach.

💻 Benchmark Python3 Implementation

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        import heapq
        h = []
        for i, node in enumerate(lists):
            if node:
                # include the index i so tuples never compare ListNode objects
                heapq.heappush(h, (node.val, i, node))
        dummy = tail = ListNode(0)
        while h:
            val, i, node = heapq.heappop(h)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(h, (node.next.val, i, node.next))
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(N log k): each of the N nodes is pushed and popped once.
💾 Space Complexity
O(k) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Pushing bare ListNode objects: when two values are equal, Python would try to compare the nodes and raise TypeError. Always include a unique tie-breaker.
  • Concatenating all lists and sorting: O(N log N) and requires O(N) extra space.
  • Merging lists pairwise in a loop: correct and O(N log k) if done as a divide-and-conquer, but O(N * k) if done naively.
  • Skipping empty lists: pushing None would break the heap; the if node guard is required.