Start learning free

LESSON 318 OF 438 · LINKED LISTS

Merge K Sorted Lists in Python: O(n × k) Scan of the Heads

Practice O(n × k) Read the full explanation

You are given a list 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] <= 107
  • 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 × k) time and use O(1) extra space apart from the merged list's new nodes (one per value), where n is the total number of nodes across all lists and k is the number of lists.
(A faster O(n log k) solution, with a min-heap, has its own lesson.)


Hints:

The output is sorted: at every moment you only need the smallest current head across all lists.
What's the simplest way to find it?

Use a dummy sentinel node and a tail walker.
Each iteration: scan all k heads, pick the smallest, append a new node with its value after tail, move tail onto it, and advance the chosen list. Repeat until every list is exhausted.

We produce n output nodes, and each one costs an O(k) scan of all heads — Time Complexity is O(n × k).
Apart from the merged list it returns (one new node per value), the solution keeps only the dummy node and a few variables, so the Extra Space is O(1).
STEP 1 OF 10
    Ctrl + Enter to check

    PYTHON · LINKED LISTS

    Merge K Sorted Lists in Python, explained

    Problem overview

    The method mergeKLists receives lists, a Python list holding k linked lists. Each linked list is sorted in ascending order and is given by its head node, or by None when it is empty. The method must return the head of one sorted linked list that contains every value from all of them.

    With lists = [1->4->5, 1->3->4, 2->6] the merged list is 1->1->2->3->4->4->5->6. If lists is empty, or holds only empty lists such as [None], the answer is an empty list, so the method returns None.

    The statement asks for O(n × k) time, where n is the total number of nodes and k is the number of lists. The extra space is O(1): the merged list is the output itself, and apart from it the code keeps only a few variables.

    Approach: always take the smallest head

    Each input list is already sorted, so its smallest unused value is always its head. The smallest unused value overall is therefore the smallest of the k heads. That gives a simple procedure: look at all the heads, take the smallest one, add it to the output, move that list forward by one node, and repeat until every list is empty.

    Each output node costs one scan of the k heads, which is O(k). There are n output nodes, so the total is O(n × k). This is the simplest correct method. Merging two lists at a time, or keeping the heads in a min-heap, brings the cost down to O(n log k), but this lesson stays with the plain scan.

    Two small tools make the code short. A dummy node sits before the real head of the output, so the first appended node needs no special case. A tail variable always points at the last node of the output, which is where the next node is attached.

    Step by step

    1. Create the dummy node. ListNode() uses the default value 0, which never appears in the answer because the result starts at dummy.next.
    2. Point tail at the dummy. Nothing has been appended yet, so the dummy is the last node of the output.
    3. Loop while any list still has nodes. any(lists) is true as soon as one entry is a node rather than None.
    4. Reset ind to -1 at the top of each pass. It holds the index of the list with the smallest head, and -1 means no list has been chosen yet.
    5. Scan every list with for i in range(len(lists)).
    6. Update the choice. A list can win only if it still has a head, and it wins if nothing has been chosen yet or its head value is strictly smaller than the current best. The strict comparison means that on a tie the earlier list keeps the win.
    7. Append a new node with the chosen value after tail.
    8. Advance the chosen list by replacing its entry with its next node.
    9. Move tail forward onto the node just appended.
    10. Return dummy.next once the loop ends: the head of the merged list, or None if nothing was ever appended.

    The solution in Python

    class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy = ListNode()
        tail = dummy
        while any(lists):
            ind = -1
            for i in range(len(lists)):
                if lists[i] and (ind == -1 or lists[i].val < lists[ind].val):
                    ind = i
            tail.next = ListNode(lists[ind].val)
            lists[ind] = lists[ind].next
            tail = tail.next
        return dummy.next

    The Python details worth a closer look:

    • Truthiness of nodes. A ListNode object is truthy, because the class defines neither __bool__ nor __len__, and None is falsy. That is why any(lists) and if lists[i] work as "is there a node here". It would break for a class that defined __len__ returning 0, but a plain node doesn't.
    • and short-circuits. In lists[i] and (ind == -1 or lists[i].val < lists[ind].val), the right side runs only when lists[i] is a node. The inner or likewise skips lists[ind].val when ind is -1. Without that order, the code would read .val on None or on lists[-1].
    • Negative indices are valid in Python. If ind were -1 when lists[ind] was read, Python wouldn't raise an error. It would silently read the last list. The loop condition guarantees that at least one list has a node, so the scan always sets ind to a real index before the append.
    • The input list is consumed. lists[ind] = lists[ind].next overwrites entries of the caller's list. After the call, lists holds only None values. The original nodes are not changed, since the method copies each value into a new ListNode, so the input chains stay intact if you kept their heads elsewhere.
    • Local names. tail and dummy refer to the same object at first. Assigning tail = tail.next rebinds only the name tail, while dummy stays at the front, which is what makes dummy.next the head at the end.

    Complexity

    Time: O(n × k). The outer loop runs once per output node, so n times. Each pass scans k entries. The call to any(lists) also looks at entries, but it stops at the first node it finds, and the scan costs O(k) anyway, so it doesn't change the bound. In the worst case any must pass over many None entries before it finds a node, which is still at most k checks per pass.

    Space: O(1) extra. The result list has one new node per value, which is the output and not working memory. Besides it, the code keeps the dummy node and the variables tail, ind and i. Nothing grows with n or k.

    Edge cases and common mistakes

    • No lists. lists = [] makes any(lists) false right away, and the method returns dummy.next, which is None.
    • Only empty lists. [None] and [None, None] behave the same way and return None.
    • Some lists empty. [None, 1->2] works because the scan skips None entries and later passes keep skipping them.
    • Duplicates and negative values. [1->1, 1] keeps every copy of 1. Values below zero, such as -7 and -5, order correctly because the code compares values and never uses them as indices.
    • Non-strict comparison. Using <= instead of < still produces a sorted list, but the tie goes to the later list. With < the earlier list wins, which keeps equal values from different lists in list order.
    • Forgetting to advance a list. If lists[ind] isn't moved forward, the same node is chosen on every pass and the loop never ends.
    • Returning dummy. That would put an extra leading node holding 0 into the answer. Return dummy.next.

    Testing

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