Merge k Sorted Lists

PracticeNeetCode ↗LeetCode ↗

Given an array of k sorted linked lists, merge them into one sorted linked list and return its head.

Example

Key Pointers

• Merging lists one-by-one costs O(kn) comparisons overall; pairing lists up and merging in rounds (divide and conquer) brings it down to O(n log k).
• Reuse the two-list merge from Merge Two Sorted Lists as the building block — no need to reinvent merging logic.
• A min-heap over the current head of each list is an equally valid O(n log k) alternative, if picking the global minimum directly each step is preferred.

Step-by-Step Analysis

1. If the list of lists is empty, return None.
2. While more than one list remains: merge lists in pairs (0 with 1, 2 with 3, …), producing half as many lists.
3. Repeat pairwise merging round after round until only one merged list remains.
4. Return that final list's head.

Complexity

Time: O(n log k) where n is total nodes, k is number of lists — Space: O(log k) for the merge rounds

Code

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

def mergeTwoLists(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 if l1 else l2
    return dummy.next

def mergeKLists(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(mergeTwoLists(l1, l2))
        lists = merged

    return lists[0]

Code Explanation

How the solution above works, piece by piece.

1. mergeTwoLists is the standard two-list merge with a dummy head.
2. while len(lists) > 1: each round pairs up lists 0+1, 2+3, …; an odd one out is merged with None, which just returns it.
3. lists = merged: the next round works on half as many lists.
4. Pairing (instead of merging lists into one growing result one by one) keeps each node's number of merges at log k rather than up to k.
5. O(N log k) time for N total nodes, O(1) extra space besides the list of heads.

Visual Walkthrough

Running it on lists = [[1, 4, 5], [1, 3, 4], [2, 6]]:

Video Explanation

NeetCode — LeetCode 23