Merge k Sorted Lists

---

Merge k Sorted Lists: 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 <= 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.

---

Try this Problem on your own or check similar problems:

1. Merge Two Sorted Lists
2. Ugly Number II
3. Smallest Subarrays With Maximum Bitwise OR

Solution:

Java

public ListNode mergeKLists(ListNode[] lists) {
    ListNode dummy = new ListNode(-1, null), iter = dummy;
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

    for(int i = 0; i < lists.length; ++i){
        if(lists[i] != null) pq.add(lists[i]);
    }

    while(!pq.isEmpty()){
        ListNode node = pq.poll();
        iter.next = node;
        if(node.next != null){
            pq.add(node.next);
        }
        iter = iter.next;
    }

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  const dummy = new ListNode(-1);
  let iter = dummy;
  const pq = new MinPriorityQueue((a) => a.val);

  for (const node of lists) {
    if (node) {
      pq.enqueue(node, node.val);
    }
  }

  while (!pq.isEmpty()) {
    const node = pq.dequeue().element;
    iter.next = node;
    if (node.next) {
      pq.enqueue(node.next, node.next.val);
    }
    iter = iter.next;
  }

  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(None)
        curr = dummy
        h = []

        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(h, (lists[i].val, i))
                lists[i] = lists[i].next

        while h:
            val, i = heapq.heappop(h)
            curr.next = ListNode(val)
            curr = curr.next
            if lists[i]:
                heapq.heappush(h, (lists[i].val, i))
                lists[i] = lists[i].next

        return dummy.next

C++

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* iter = dummy;
        priority_queue<ListNode*, vector<ListNode*>, compare> pq;

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

        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            iter->next = node;
            if (node->next) {
                pq.push(node->next);
            }
            iter = iter->next;
        }

        return dummy->next;
    }

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

---

Time/Space Complexity:

• Time Complexity: O(nlogk) where k is the number of lists
• Space Complexity: O(k)

---

Explanation:

For the time complexity we have O(nlogk) where logk is needed for polling and inserting a node in the queue of maximum size k (the maximum size is determined by the number of lists, since the queue will be the longest after the first loop once we have placed head nodes of each list), while n is the total number of nodes in the merged list (sum of lengths of all linked lists). For space complexity we have the queue of maximum size k. We solve the problem by using minheap and first inserting all heads of all lists as our first candidates. We then keep on polling until there is no element left in the queue, which means we have merged all the nodes from all lists. When we poll a node, we know it's the node with the smallest value, so it makes sense to insert the next (if there is one) element from the linked list inserted node is coming from, back in the queue. Each iteration we will be polling the smallest value node and end up with sorted merged list. This problem can be solved without any additional space complexity if we utilized the algorithm for Merge Two Sorted Lists where we merge bigger and bigger parts of the lists until we reach point where we're merging only two sorted lists:

Java

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
      if(lists.length == 0){
          return null;
      }

      int interval = 1;
      while(interval < lists.length){
          for (int i = 0; i + interval < lists.length; i = i + interval * 2) {
              lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
          }
          interval *= 2;
      }

      return lists[0];
  }

  private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if(list1 == null || list2 == null) return list1 == null ? list2 : list1;

      ListNode dummy = new ListNode(-1, null), curr = dummy;

      while(list1 != null && list2 != null){
          if(list1.val < list2.val){
              curr.next = list1;
              list1 = list1.next;
          }
          else{
              curr.next = list2;
              list2 = list2.next;
          }

          curr = curr.next;
      }

      if(list1 != null || list2 != null){
          curr.next = list1 != null ? list1 : list2;
      }

      return dummy.next;
  }
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (lists.length === 0) {
    return null;
  }

  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }

  return lists[0];
};

function mergeTwoLists(list1, list2) {
  if (list1 === null || list2 === null) {
    return list1 === null ? list2 : list1;
  }

  let dummy = new ListNode(-1);
  let curr = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }

    curr = curr.next;
  }

  if (list1 !== null || list2 !== null) {
    curr.next = list1 !== null ? list1 : list2;
  }

  return dummy.next;
}

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None

        interval = 1
        while interval < len(lists):
            for i in range(0, len(lists) - interval, interval * 2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])
            interval *= 2

        return lists[0]

    def mergeTwoLists(self, list1, list2):
        if list1 is None or list2 is None:
            return list1 if list1 is not None else list2

        dummy = ListNode(-1, None)
        curr = dummy

        while list1 is not None and list2 is not None:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next

            curr = curr.next

        if list1 is not None or list2 is not None:
            curr.next = list1 if list1 is not None else list2

        return dummy.next

C++

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }

        int interval = 1;
        while (interval < lists.size()) {
            for (int i = 0; i + interval < lists.size(); i += interval * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }

private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr || list2 == nullptr) {
            return list1 == nullptr ? list2 : list1;
        }

        ListNode dummy(0);
        ListNode* curr = &dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }

        curr->next = list1 != nullptr ? list1 : list2;

        return dummy.next;
    }
};

We keep on doubling the interval, so for the first iteration we will be merging lists in pairs, and we will end up with n/2 lists which we will then merge to get n/4 lists until there is only list left. It takes at most n nodes to merge the last two halves, and we have log n lists (each time halving the total number of lists) leading to O(nlogn) time complexity. Note again that n is the total number of nodes in all lists.