23. Merge k Sorted Lists

by

23. Merge k Sorted Lists

Hard

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 won’t exceed 10^4.

思路

类似分治法的思想，每次从 to_merge 中取两个列表合并，合并后存入临时结果 merge_buf。

to_merge 遍历完成后，merge_buf 成为下轮的 to_merge。

当 to_merge 中只剩一个列表时终止循环，返回该列表。

/**
 * 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) {}
 * };
 */

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
    ListNode *result_head = new ListNode();
    ListNode *cursor = result_head;
    while (a != nullptr && b != nullptr) {
        if (a->val > b->val) {
            cursor->next = b;
            cursor = cursor->next;
            b = b->next;
        }
        else {
            cursor->next = a;
            cursor = cursor->next;
            a = a->next;
        }
    }
    if (a != nullptr) {
        while (a != nullptr) {
            cursor->next = a;
            cursor = cursor->next;
            a = a->next;
        }
    }
    else {
        while (b != nullptr) {
            cursor->next = b;
            cursor = cursor->next;
            b = b->next;
        }
    }
    ListNode *result = result_head->next;
    delete result_head;
    return result;
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) {
            return nullptr;
        }
        vector<ListNode*> *to_merge = new vector<ListNode*>(lists);
        int to_merge_size = to_merge->size();
        vector<ListNode*> *merge_buf = new vector<ListNode*>();
        while (to_merge_size > 1) {
            for (int i = 0; i < to_merge_size - 1; i += 2) {
                merge_buf->emplace_back(mergeTwoLists((*to_merge)[i], (*to_merge)[i + 1]));
            }
            if (to_merge_size % 2 == 1) {
                merge_buf->emplace_back((*to_merge)[to_merge_size - 1]);
            }
            vector<ListNode*> *tmp;
            tmp = to_merge;
            to_merge = merge_buf;
            to_merge_size = to_merge->size();
            merge_buf = tmp;
            merge_buf->clear();
        }
      	ListNode* result = (*to_merge)[0];
        delete to_merge;
      	delete merge_buf;
        return result;
    }
};

Runtime: 12 ms, faster than 99.69% of C++ online submissions for Merge k Sorted Lists.

Memory Usage: 13.6 MB, less than 35.98% of C++ online submissions for Merge k Sorted Lists.

Leave a Comment