Start learning free

LESSON 311 OF 415 · LINKED LISTS

Merge K Sorted Lists in Swift: 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 the node's value.
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 11
    Ctrl + Enter to check

    SWIFT · LINKED LISTS

    Merge K Sorted Lists in Swift, explained

    Problem overview

    The method mergeKLists receives an array lists of k linked lists, each sorted in ascending order. Some of the entries can be empty, so the array has type [ListNode?]. The method returns one sorted list that contains every value from all the lists, or nil if there are none.

    In the first example, [1, 4, 5], [1, 3, 4] and [2, 6] merge into [1, 1, 2, 3, 4, 4, 5, 6]. An empty array gives an empty list, and an array holding one empty list gives an empty list too.

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

    Approach: always take the smallest head

    Each list is sorted, so the smallest value that is not yet in the result is always at the head of one of the lists. The merged list can therefore be built by repeating one step: find the smallest head among the k lists, append it, and move that list forward.

    Scanning all k heads each time costs O(k) per output node, which gives O(n * k) overall. A min-heap does the same job faster. It is a collection that always gives back its smallest element, and both inserting and removing the smallest take O(log k). The heap here never holds more than one node per list, so it never has more than k entries.

    The process looks like this on the first example. The heap starts with the heads 1, 1 and 2. Remove a 1 and append it; that list's next node, 4, joins the heap. The smallest is now the other 1, whose successor 3 joins. Then 2 comes out and its successor 6 joins, and so on, until the heap is empty and the result is complete.

    Step by step

    1. Create the heap. Swift has no built-in priority queue, so the lesson provides a MinHeap value type that orders ListNode objects by their val. Call it minNodes. It is a var, because pushing and popping are mutating methods.
    2. Visit every list head with for head in lists.
    3. Push the non-empty ones. if let head = head unwraps the optional, so an empty list is skipped, and the heap starts with the heads of all non-empty lists.
    4. Create a dummy node dummy. The merged list will be dummy.next, which avoids a special case for the first node.
    5. Keep a walker var tail = dummy that points at the last appended node.
    6. Loop while the heap has entries, that is, while minNodes.count > 0. Each iteration produces one node of the output and costs O(log k).
    7. Pop the smallest node into minNode.
    8. Append a copy of its value: tail.next = ListNode(minNode.val).
    9. Feed the heap. If minNode has a successor, unwrap it with if let next = minNode.next and push it. A list keeps supplying nodes until it is used up.
    10. Advance the walker with tail = tail.next!. The value was assigned one statement earlier, so the force-unwrap is safe.
    11. Return dummy.next, the head of the merged list.

    The solution in Swift

    class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        var minNodes = MinHeap()
        for head in lists {
            if let head = head {
                minNodes.push(head)
            }
        }
        let dummy = ListNode()
        var tail = dummy
        while minNodes.count > 0 {
            let minNode = minNodes.pop()
            tail.next = ListNode(minNode.val)
            if let next = minNode.next {
                minNodes.push(next)
            }
            tail = tail.next!
        }
        return dummy.next
    }
}

    Swift details worth knowing:

    • if let head = head. This unwraps an optional and names the result with the same name. Inside the braces, head is a plain ListNode, so it can be pushed without !. The loop variable head is an optional, and the unwrapped one shadows it.
    • Value type, mutating methods. MinHeap is a struct, so the constant form let minNodes would not allow push or pop. That's why it is a var.
    • New nodes, untouched inputs. The solution builds ListNode(minNode.val) instead of relinking the original nodes, so the input lists are left exactly as they were. The cost is n new nodes, which the output needs anyway; the extra working memory is just the heap.
    • The list type is a class. The heap stores references to the lists' own nodes. Reading minNode.next after the pop still reaches the rest of that list.
    • minNodes.count > 0. Swift requires a Bool condition, so the check is explicit. An integer alone would not compile as a condition.

    Complexity

    Time: O(n log k). Pushing the first heads costs at most k pushes of O(log k) each. Each of the n output nodes needs one pop and at most one push, each O(log k), because the heap never holds more than k nodes. That is O(n log k) in total.

    Space: O(k) extra. The heap holds at most one node per list. The merged list itself is the output.

    Edge cases and common mistakes

    • No lists. [] leaves the heap empty, the loop never runs, and dummy.next is nil.
    • Only empty lists. An array like [nil] behaves the same way, because empty heads are never pushed.
    • Some lists empty. [nil, [2], nil, [-1, 3]] gives [-1, 2, 3]. Skipping the nil heads is what if let is for.
    • Duplicates. Equal values are fine: [1, 4, 5] and [1, 3, 4] produce both 1s and both 4s.
    • Forgetting the successor. If the popped node's next isn't pushed, the result would hold only the first node of each list.
    • Pushing every node at the start. That would work but would make the heap size n instead of k, so the time is O(n log n) and the space O(n).
    • Returning dummy. The dummy holds a meaningless 0 and would appear as the first value.

    Testing

    • [[1, 4, 5], [1, 3, 4], [2, 6]] gives [1, 1, 2, 3, 4, 4, 5, 6].
    • [] gives [].
    • [[]] gives [].
    • [[], [2], [], [-1, 3]] gives [-1, 2, 3].
    • [[1, 2], [3]] gives [1, 2, 3], and the two input lists still read [1, 2] and [3] afterwards.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free