[/dsa/leetcode]

23 - Merge k Sorted Lists

Saturday, 19 September 2026

<hard> [problem]

Merging the lists one at a time walks the growing result k times over - pair them up and halve the count each round instead, and log k rounds finish it.

{linked list}{divide and conquer}{heap}

Problem

You are given an array of k linked lists, each sorted in ascending order. Merge all the lists into one sorted linked list and return it.

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

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

Constraints:

  • k == lists.length, with 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500, values in [-10^4, 10^4], each list sorted ascending
  • The total number of nodes will not exceed 10^4

Approach

[A] [B] [C] [D] [E]

round 1   (A+B) (C+D) (E)       5 -> 3      every node touched once
round 2   (AB+CD) (E)           3 -> 2      every node touched once
round 3   (ABCD+E)              2 -> 1      every node touched once

O(n) per round, log k rounds  ->  O(n log k)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        while (lists.size() > 1) {
            vector<ListNode*> temp;
            for (size_t i = 0; i < lists.size(); i += 2) {
                ListNode* l1 = lists[i];
                ListNode* l2 = i + 1 < lists.size() ? lists[i + 1] : nullptr;
                temp.push_back(mergeLists(l1, l2));
            }
            lists = move(temp);
        }

        return lists[0];
    }

private:
    ListNode* mergeLists(ListNode* l1, ListNode* l2) {
        ListNode dummy;
        ListNode* node = &dummy;

        while (l1 && l2) {
            if (l1->val > l2->val) {
                node->next = l2;
                l2 = l2->next;
            } else {
                node->next = l1;
                l1 = l1->next;
            }
            node = node->next;
        }

        node->next = l1 ? l1 : l2;
        return dummy.next;
    }
};
  • time: O(n log k) - log k rounds, every node touched once per round
  • space: O(k) - the temp vector of heads; the merge itself is O(1)
quantinium © 2026