Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 12

Description

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 <= 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.

Solution

class Solution {
  ListNode *merge2Lists(ListNode *a, ListNode *b) {
    ListNode *newHead = new ListNode(0);
    ListNode *cur = newHead;
    while(a && b) {
      if(a->val < b->val) {
        cur->next = a;
        a = a->next;
      } else {
        cur->next = b;
        b = b->next;
      }
      cur = cur->next;
    }
    if(a) cur->next = a;
    else cur->next = b;
    return newHead->next;
  }
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.empty()) return nullptr;
    int len = lists.size();
    for(int step = 1; step < len; step <<= 1) {
      for(int first = 0; first + step < len; first += 2 * step) {
        lists[first] = merge2Lists(lists[first], lists[first + step]);
      }
    }
    return lists.front();
  }
};

// Accepted
// 133/133 cases passed (12 ms)
// Your runtime beats 99.77 % of cpp submissions
// Your memory usage beats 58.51 % of cpp submissions (13.3 MB)