Start learning free

LESSON 323 OF 443 · LINKED LISTS

Merge K Sorted Lists in Swift: O(n × k) by Scanning the Heads

Practice O(n × 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] <= 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 14
    Ctrl + Enter to check

    SWIFT · LINKED LISTS

    Merge K Sorted Lists in Swift, explained

    Problem overview

    The method mergeKLists receives an array of k linked lists, each sorted in ascending order, as [ListNode?]. Each element is the head node of a list, or nil for an empty list. The method merges them all into one sorted linked list and returns its head, or nil when there is nothing to merge.

    For the lists 1->4->5, 1->3->4 and 2->6, the merged list is 1->1->2->3->4->4->5->6. For an empty array, and for an array holding one empty list, the result is an empty list.

    This lesson asks for O(n × k) time, where n is the total number of nodes and k is the number of lists. A faster O(n log k) approach with a min-heap is a separate lesson.

    Approach: repeatedly take the smallest head

    Because every input list is sorted, the smallest number not yet used is always at the front of one of the lists. So the merged list can be built one node at a time: look at the head of every list, pick the smallest, append its value to the output, and advance that list by one node. Repeat until every list is exhausted.

    Finding the smallest head means scanning all k lists, which costs O(k). That scan happens once per output node, so with n nodes the total is O(n × k). It is easy to get right, and it is the baseline that the heap version improves.

    Two details make the code short. The first is a dummy node placed in front of the output. Appending to the end of a list needs a special case when the list is empty, since there is no last node yet. With a dummy node there is always a last node, and the real head is dummy.next at the end. The second is a tail variable that always refers to the last node appended.

    The loop needs to know when to stop, which is when every entry of the array is nil. A small helper, anyNonNull, answers that.

    Step by step

    1. Create the dummy node with let dummy = ListNode(). It is a let because the variable never points to a different node; the node's next field is what changes.
    2. Keep a tail with var tail = dummy. It starts at the dummy and moves to each node as it is appended.
    3. Loop while any list has nodes: while anyNonNull(lists). The helper is written last.
    4. Prepare to pick a winner. var ind = -1 stores the index of the list with the smallest head. The value -1 means that no list has been picked yet.
    5. Scan every list with for i in 0..<lists.count. This scan is the O(k) part.
    6. Update the winner. List i becomes the new candidate when it is not nil and either nothing has been picked yet or its head value is strictly smaller than the current best. The test on -1 comes first so that lists[ind] is never read with an invalid index.
    7. Append a node with the winning value: tail.next = ListNode(lists[ind]!.val).
    8. Advance the winning list with lists[ind] = lists[ind]!.next. Its next node, possibly nil, becomes its new head.
    9. Move the tail onto the node just appended: tail = tail.next!.
    10. Return dummy.next after the loop. That is the first real node, or nil if nothing was appended.
    11. Write the helper anyNonNull, which receives the array and returns a Bool.
    12. Loop over the entries with for l in lists.
    13. Return true at the first non-nil entry. One live list is enough to answer the question.
    14. Return false after the loop. Every entry was nil.

    The solution in Swift

    class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        var lists = lists
        let dummy = ListNode()
        var tail = dummy
        while anyNonNull(lists) {
            var ind = -1
            for i in 0..<lists.count {
                if lists[i] != nil && (ind == -1 || 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
    }

    func anyNonNull(_ lists: [ListNode?]) -> Bool {
        for l in lists {
            if l != nil {
                return true
            }
        }
        return false
    }
}

    The Swift details worth a closer look:

    • var lists = lists. Function parameters are constants, but the loop needs to move each list's head forward. Declaring a local var with the same name shadows the parameter with a mutable copy. An array is a value type, so the caller's array is not affected. The nodes themselves are never modified either, only the references in the local array.
    • Optionals everywhere. ListNode? is either a node or nil. Comparing with lists[i] != nil checks for a node without unwrapping it. The exclamation mark in lists[i]!.val unwraps the optional and crashes if it is nil, so each ! in the solution is guarded by an earlier check.
    • Short-circuit && and ||. In lists[i] != nil && (...), the right side runs only if the left side is true, so lists[i]! is safe. In ind == -1 || lists[i]!.val < lists[ind]!.val, the right side runs only when ind is a valid index.
    • The result is a new list. ListNode(lists[ind]!.val) copies the value into a fresh node, so the merged list shares no nodes with the inputs. After merging [1, 2] alone, the returned head is a different object from the input head, and the input list still reads [1, 2].
    • tail = tail.next! is safe because the line above has just set tail.next to a new node.
    • Strict < keeps ties in input order. When two heads are equal, the earlier list keeps the win, so equal values leave the lists in the order the lists were given.

    Complexity

    Time: O(n × k). The outer loop runs once per output node, so n times. Each pass scans k heads and calls anyNonNull, which looks at up to k entries. That is O(k) per pass.

    Space: O(k) beyond the returned list. The merged list needs one new node per value, as it must be returned. The extra bookkeeping is the dummy node, a few variables and the local copy of the array of heads, which holds k references.

    Edge cases and common mistakes

    • No lists. [] makes anyNonNull false at once, and the method returns dummy.next, which is nil.
    • Only empty lists. [nil] behaves the same way and also returns nil.
    • Empty lists mixed with others. For [nil, 2, nil, -1->3] the scan skips the nil entries and the result is -1->2->3. The != nil test in the scan is what makes that safe.
    • Negative values. Picking the first non-empty list as the starting winner, through ind == -1, works for any value. Starting with a "smallest so far" of 0 would go wrong for negative inputs.
    • Reading lists[ind] while ind is -1. Swift stops the program with an index-out-of-range error. The ind == -1 || check prevents it.
    • Forgetting to advance the chosen list. The loop would pick the same node forever, because anyNonNull never becomes false.
    • Returning dummy. The dummy node's value is a placeholder, and the answer starts at dummy.next.

    Testing

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