</>Ali · LeetCode
#0023·HardLinked Lists

Merge k Sorted Lists

LeetCode #23 · Hard · Linked Lists · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Frequency Map (Using std::map)

Strategy

  1. 1Use a frequency map (ordered by key) to store counts of all values in
  2. 2Traverse each linked list once to populate the map.
  3. 3Construct a new linked list by iterating through the map in ascending
Time
O(N log M)
N is total nodes and M is absolute range or unique count.
Space
O(M)
the map.
Problem description(from LeetCode)

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.

Examples

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

Constraints

  • •k == lists.length
  • •0 <= k <= 10^4
  • •0 <= lists[i].length <= 500
  • •-10^4 <= lists[i][j] <= 10^4
  • •lists[i] is sorted in ascending order.
  • •The sum of lists[i].length will not exceed 10^4.

C++ Solution

solution.cpp
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct compare {
    bool operator()(ListNode *a, ListNode *b) { return a->val > b->val; }
  };

  ListNode *mergeKListsOptimized(vector<ListNode *> &lists) {
    priority_queue<ListNode *, vector<ListNode *>, compare> pq;

    for (ListNode *list : lists) {
      if (list) pq.push(list);
    }

    ListNode *dummy = new ListNode(0);
    ListNode *tail = dummy;

    while (!pq.empty()) {
      ListNode *top = pq.top();
      pq.pop();

      tail->next = top;
      tail = tail->next;

      if (top->next) pq.push(top->next);
    }

    return dummy->next;
  }
};

class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
    map<int, int> mp;
    for (ListNode *list : lists) {
      ListNode *temp = list;
      while (temp != nullptr) {
        mp[temp->val]++;
        temp = temp->next;
      }
    }

    if (mp.empty()) return nullptr;

    ListNode *dummy = new ListNode(0);
    ListNode *tail = dummy;
    for (auto &[num, count] : mp) {
      while (count--) {
        tail->next = new ListNode(num);
        tail = tail->next;
      }
    }

    return dummy->next;
  }

  /*
   * Approach 2: Optimized using Priority Queue (Min-Heap)
   *
   * Strategy:
   * 1. Use a min-heap to store the head of each list.
   * 2. Repeatedly extract the smallest node from the heap and add it to the
   * merged list.
   * 3. If the extracted node has a next node, add that next node to the heap.
   *
   * Time Complexity: O(N log k) where N is the total number of nodes and k is
   * the number of lists.
   * Space Complexity: O(k) for the priority queue.
   */
  struct compare {
    bool operator()(ListNode *a, ListNode *b) { return a->val > b->val; }
  };

  ListNode *mergeKListsOptimized(vector<ListNode *> &lists) {
    priority_queue<ListNode *, vector<ListNode *>, compare> pq;

    for (ListNode *list : lists) {
      if (list) pq.push(list);
    }

    ListNode *dummy = new ListNode(0);
    ListNode *tail = dummy;

    while (!pq.empty()) {
      ListNode *top = pq.top();
      pq.pop();

      tail->next = top;
      tail = tail->next;

      if (top->next) pq.push(top->next);
    }

    return dummy->next;
  }
};

More Linked Lists problems