LeetCode 23: Merge k Sorted Lists Solution in Python Explained

Problem Statement

LeetCode 23, Merge k Sorted Lists, is a hard-level challenge where you’re given an array of k sorted linked lists, lists, and need to merge them into one sorted linked list. Each list is sorted in non-decreasing order, and your task is to return the head of the merged list. The lists can be empty, and k ranges from 0 to 10^4, making efficiency crucial.

Constraints

  • k == lists.length: Number of lists.
  • 0 <= k <= 10^4: From 0 to 10,000 lists.
  • 0 <= lists[i].length <= 500: Each list has 0 to 500 nodes.
  • -10^4 <= lists[i].val <= 10^4: Node values range from -10,000 to 10,000.
  • Sum of all list lengths ≤ 10^6.

Example

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Merge all lists into one sorted list.

Input: lists = []
Output: []
Explanation: Empty array returns null.

Input: lists = [[], [1]]
Output: [1]
Explanation: Merge empty list with [1].

Understanding the Problem

How do you solve LeetCode 23: Merge k Sorted Lists in Python? Imagine you have three sorted lists: [1,4,5], [1,3,4], and [2,6]. You need to combine them into [1,1,2,3,4,4,5,6], maintaining order. With k lists, a naive approach (merging one-by-one) is slow, so we’ll explore two efficient methods: a Priority Queue (Heap) Approach (optimal) and a Merge Sort (Divide and Conquer) Approach.

Solution 1: Priority Queue (Heap) Approach (Primary)

Explanation

Use a min-heap to keep track of the smallest unprocessed node from each list. Pop the smallest node, add it to the merged list, and push its next node into the heap, repeating until all nodes are processed.

Here’s a visual for [[1,4],[2,3]]:

Heap: [(1,list1),(2,list2)]
Pop 1 → Add 1, push 4 → Heap: [(2,list2),(4,list1)]
Pop 2 → Add 2, push 3 → Heap: [(3,list2),(4,list1)]
Pop 3 → Add 3 → Heap: [(4,list1)]
Pop 4 → Add 4 → Heap: []
Merged: 1 -> 2 -> 3 -> 4
  1. Handle Edge Case.
  • If lists empty or all null, return null.
  1. Initialize Heap.
  • Add first node of each non-empty list to heap with value and list index.
  1. Build Merged List.
  • Pop smallest node, link it, push its next node if exists.
  1. Return Head.
  • Return merged list head.

Step-by-Step Example

Example 1: lists = [[1,4,5],[1,3,4],[2,6]]

We have [[1,4,5],[1,3,4],[2,6]], target merged list.

  • Goal: Merge into [1,1,2,3,4,4,5,6].
  • Result for Reference: [1,1,2,3,4,4,5,6].
  • Start: Dummy node, heap empty, result empty.
  • Step 1: Check empty.
    • 3 lists, not empty, proceed.
  • Step 2: Initialize heap.
    • Add (1,0) for list[0], (1,1) for list[1], (2,2) for list[2].
    • Heap: [(1,0),(1,1),(2,2)].
  • Step 3: Pop smallest (1,0).
    • Value 1, link to dummy.next, list[0] moves to 4.
    • Push (4,0), heap: [(1,1),(4,0),(2,2)].
    • List: dummy -> 1.
  • Step 4: Pop (1,1).
    • Value 1, link, list[1] to 3.
    • Push (3,1), heap: [(2,2),(4,0),(3,1)].
    • List: dummy -> 1 -> 1.
  • Step 5: Pop (2,2).
    • Value 2, link, list[2] to 6.
    • Push (6,2), heap: [(3,1),(4,0),(6,2)].
    • List: dummy -> 1 -> 1 -> 2.
  • Step 6: Pop (3,1).
    • Value 3, link, list[1] to 4.
    • Push (4,1), heap: [(4,0),(4,1),(6,2)].
    • List: dummy -> 1 -> 1 -> 2 -> 3.
  • Step 7: Pop (4,0).
    • Value 4, link, list[0] to 5.
    • Push (5,0), heap: [(4,1),(6,2),(5,0)].
    • List: dummy -> 1 -> 1 -> 2 -> 3 -> 4.
  • Step 8: Pop (4,1).
    • Value 4, link, list[1] to null.
    • Heap: [(5,0),(6,2)].
    • List: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4.
  • Step 9: Pop (5,0).
    • Value 5, link, list[0] to null.
    • Heap: [(6,2)].
    • List: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5.
  • Step 10: Pop (6,2).
    • Value 6, link, list[2] to null.
    • Heap empty.
    • List: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.
  • Finish: Return dummy.next: [1,1,2,3,4,4,5,6].

How the Code Works (Priority Queue)

Here’s the Python code with line-by-line explanation:

from heapq import heappush, heappop

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

def mergeKLists(lists: list[ListNode]) -> ListNode:
    # Line 1: Handle edge case - empty or all null lists
    if not lists or all(l is None for l in lists):
        # Line 2: Return null if no lists or all empty
        return None

    # Line 3: Create dummy node for merged list
    dummy = ListNode(0)
    # Line 4: Current pointer starts at dummy
    current = dummy
    # Line 5: Initialize min-heap
    heap = []

    # Line 6: Add first node of each list to heap
    for i, lst in enumerate(lists):
        # Line 7: Skip null lists
        if lst:
            # Line 8: Push (value, index, node) to heap
            heappush(heap, (lst.val, i, lst))

    # Line 9: Process heap until empty
    while heap:
        # Line 10: Pop smallest node (value, index, node)
        val, i, node = heappop(heap)
        # Line 11: Link current to this node
        current.next = node
        # Line 12: Move current forward
        current = current.next
        # Line 13: If node has next, push it to heap
        if node.next:
            # Line 14: Add next node with same index
            heappush(heap, (node.next.val, i, node.next))

    # Line 15: Return head of merged list
    return dummy.next

Alternative: Merge Sort (Divide and Conquer)

Explanation

Divide the list of k lists into pairs, merge them recursively like merge sort, and combine results until one list remains. This uses a helper to merge two lists iteratively.

  1. Base Cases.
  • Empty or single list returns as-is.
  1. Divide.
  • Split lists into two halves recursively.
  1. Conquer.
  • Merge pairs using a two-list merge function.
  1. Return Result.
  • Return final merged list head.

Step-by-Step Example (Merge Sort)

For lists = [[1,4,5],[1,3,4],[2,6]]:

  • Goal: Merge to [1,1,2,3,4,4,5,6].
  • Result for Reference: [1,1,2,3,4,4,5,6].
  • Start: Call mergeKLists([list0, list1, list2]).
  • Step 1: Divide 3 lists.
    • Split: [list0], [list1, list2].
  • Step 2: Base case [list0] = [1,4,5].
    • Return [1,4,5].
  • Step 3: Divide [list1, list2].
    • Split: [list1], [list2].
    • Return list1 = [1,3,4], list2 = [2,6].
  • Step 4: Merge [1,3,4] and [2,6].
    • Dummy -> 1 -> 2 -> 3 -> 4 -> 6.
  • Step 5: Merge [1,4,5] and [1,2,3,4,6].
    • Dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.
  • Finish: Return [1,1,2,3,4,4,5,6].

How the Code Works (Merge Sort)

Here’s the Python code with explanations:

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

def mergeKLists(lists: list[ListNode]) -> ListNode:
    # Line 1: Helper to merge two sorted lists
    def mergeTwo(l1: ListNode, l2: ListNode) -> ListNode:
        # Line 2: Dummy node for merged list
        dummy = ListNode(0)
        # Line 3: Current pointer
        current = dummy
        # Line 4: Merge while both have nodes
        while l1 and l2:
            # Line 5: Compare and link smaller value
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            # Line 6: Move current forward
            current = current.next
        # Line 7: Append remaining from l1
        if l1:
            current.next = l1
        # Line 8: Append remaining from l2
        if l2:
            current.next = l2
        # Line 9: Return merged list head
        return dummy.next

    # Line 10: Handle edge cases
    if not lists:
        # Line 11: Empty array returns null
        return None
    if len(lists) == 1:
        # Line 12: Single list returns itself
        return lists[0]

    # Line 13: Divide lists into two halves
    mid = len(lists) // 2
    # Line 14: Recursively merge left half
    left = mergeKLists(lists[:mid])
    # Line 15: Recursively merge right half
    right = mergeKLists(lists[mid:])
    # Line 16: Merge the two halves
    return mergeTwo(left, right)

Complexity

  • Priority Queue:
    • Time: O(N log k) – N total nodes, k lists in heap.
    • Space: O(k) – Heap size.
  • Merge Sort:
    • Time: O(N log k) – k levels of merging, N nodes each.
    • Space: O(log k) – Recursion stack.

Efficiency Notes

Both solutions achieve O(N log k), but Priority Queue is often faster in practice due to heap operations, while Merge Sort leverages recursive simplicity with slightly more overhead.

Key Insights

Tips to master LeetCode 23:

  • Heap for Speed: Priority queue picks smallest nodes fast—ideal for k lists.
  • Divide Smart: Merge sort splits work evenly—recursive elegance shines.
  • Skip Nulls: Handle empty lists early to avoid edge case issues.

Additional Example

For lists = [[1,3],[2]], target = merged list:

  • Goal: Merge to [1,2,3].
  • Heap: Heap [(1,0),(2,1)] -> 1 -> 2 -> 3.
  • Merge Sort: Merge [1,3] and [2] -> [1,2,3].
  • Result: [1,2,3].

Edge Cases

  • Empty Array: [] – Returns null.
  • Single List: [[1,2]] – Returns [1,2].
  • All Empty: [[],[]] – Returns null.

Final Thoughts

Both Priority Queue and Merge Sort solve LeetCode 23 efficiently in Python. Heap excels in speed, while merge sort offers clarity. Check LeetCode 21: Merge Two Sorted Lists for simpler merging practice!