Start learning free

LESSON 282 OF 344 · LINKED LISTS

Merge K Sorted Lists in Python: O(n log k) with a Min-Heap

Practice O(N log k) Read the full explanation

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Note:

Your algorithm should run in O(n log k) time and use O(k) extra space, where n is the total number of nodes across all lists and k is the number of lists.


Hints:

The brute force re-scans every list head each time. What data structure gives you the smallest of k values in O(log k) instead of O(k)?

Use a min-heap seeded with the head of every non-empty list, ordered by node.val.
Each iteration: extract the smallest node, append a copy of its value to the merged tail, and if it has a successor, push that successor onto the heap.
When the heap is empty, every list has been fully consumed.

The heap holds at most k nodes at any time. Each of the n output nodes costs one extract and at most one insert, each O(log k) — Time Complexity is O(n log k).
The heap itself uses O(k) extra space.

STEP 1 OF 12
    Ctrl + Enter to check

    PYTHON · LINKED LISTS

    Merge K Sorted Lists in Python, explained

    Problem overview

    The method mergeKLists receives lists, a Python list of k linked lists. Each linked list is sorted in ascending order and is given by its head node, or None if it is empty. The method returns the head of one linked list that holds all the values in sorted order.

    For [1 → 4 → 5, 1 → 3 → 4, 2 → 6] the merged list is 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. With no lists at all, or with a single empty list, the answer is an empty list, which is None.

    The statement asks for O(n log k) time and O(k) extra space, where n is the total number of nodes.

    Approach: always take the smallest of the k heads

    The smallest remaining value overall is always at the front of one of the lists. A simple method scans all k heads every time to find it. That costs O(k) per output node, O(n · k) in total.

    A min-heap does the same job faster. It keeps the smallest item at the top and can insert and remove in O(log k). Put the head of every non-empty list in the heap. Repeatedly remove the smallest node and add it to the result. Then add that node's successor, if any, to the heap, so its list stays represented. When the heap is empty, every list has been consumed.

    The heap never holds more than one node per list, so its size is at most k. Each of the n output nodes costs one removal and at most one insertion, each O(log k), which gives O(n log k).

    Step by step

    1. Create the heap. minNodes is a plain Python list. The heapq functions treat a list as a heap.
    2. Store tuples, not nodes. heapq orders items with <, and ListNode doesn't define it. Comparing two nodes raises TypeError. So each entry is (val, counter, node), which compares by val first.
    3. Add a tiebreaker counter. counter = 0. Tuples compare element by element, and when two vals are equal the comparison moves on to the second element. Because every counter value is different, it decides before the node is ever compared.
    4. Loop over the heads with for head in lists.
    5. Push the non-empty ones. If head isn't None, push (head.val, counter, head) and add 1 to counter.
    6. Create a dummy node with ListNode(). The merged list will hang off dummy.next, which avoids a special case for the first node.
    7. Keep a tail pointer starting at the dummy, always the last node appended.
    8. Loop while minNodes is non-empty. An empty list is false in Python, so while minNodes: is the whole test.
    9. Pop the smallest entry and unpack it into val, _ and minNode. The underscore marks the counter as unused.
    10. Append a new node holding val to the result: tail.next = ListNode(val).
    11. Feed the heap. If minNode.next exists, push (minNode.next.val, counter, minNode.next) and increase counter.
    12. Advance tail to the node just added.
    13. Return dummy.next, the head of the merged list.

    The solution in Python

    class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        minNodes = []
        counter = 0
        for head in lists:
            if head:
                heapq.heappush(minNodes, (head.val, counter, head))
                counter += 1
        dummy = ListNode()
        tail = dummy
        while minNodes:
            val, _, minNode = heapq.heappop(minNodes)
            tail.next = ListNode(val)
            if minNode.next:
                heapq.heappush(minNodes, (minNode.next.val, counter, minNode.next))
                counter += 1
            tail = tail.next
        return dummy.next

    Python details that matter:

    • heapq is a min-heap on a list. heappush and heappop keep minNodes[0] the smallest entry. The list itself isn't sorted, only arranged so that the smallest is first. Use these functions rather than reading or sorting the list yourself. The module comes from import heapq.
    • Tuple comparison. (1, 0, a) < (1, 1, b) is decided by the second elements, so a and b are never compared. Without the counter, two lists whose heads share a value would crash with TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'.
    • Truthiness of nodes. if head: is false only for None, because a node object is true unless the class defines otherwise. A node holding the value 0 is still true; the test looks at the node, not at val.
    • New nodes. The result is built from fresh ListNode(val) objects instead of relinking the originals. The input lists stay untouched, at the cost of memory for the output.

    Complexity

    Time: O(n log k). Building the heap takes at most k pushes, each O(log k). The main loop runs n times with one pop and at most one push, each O(log k).

    Space: O(k) extra, for the heap of at most k entries. The merged list holds n new nodes, but that is the output, not working storage.

    Edge cases and common mistakes

    • No lists. [] leaves the heap empty, the loop never runs, and dummy.next is None.
    • Only empty lists. [None] gives None in the same way.
    • Equal values across lists. Two heads with the same value work because of the counter. This is the most common crash in heap solutions.
    • Pushing bare nodes or (val, node) pairs. Both fail on ties with a TypeError.
    • Pushing a node that is None. Without the if head: and if minNode.next: checks, None.val raises AttributeError.
    • Returning dummy. The dummy node is a placeholder. The answer starts at dummy.next.
    • Skipping the successor push. Without it, each list contributes only its first node.

    Testing

    • [1 → 4 → 5, 1 → 3 → 4, 2 → 6] gives 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6.
    • [] gives an empty list.
    • [None] gives an empty list.
    • [1 → 1, 1] gives 1 → 1 → 1, which exercises ties.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free