LeetCode-in-Cpp

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.

Solution

#include <vector>
using namespace std;

/**
 * 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;
        }
        return mergeKLists(lists, 0, lists.size());
    }

private:
    ListNode* mergeKLists(vector<ListNode*>& lists, int leftIndex, int rightIndex) {
        if (rightIndex > leftIndex + 1) {
            int mid = (leftIndex + rightIndex) / 2;
            ListNode* left = mergeKLists(lists, leftIndex, mid);
            ListNode* right = mergeKLists(lists, mid, rightIndex);
            return mergeTwoLists(left, right);
        } else {
            return lists[leftIndex];
        }
    }

    ListNode* mergeTwoLists(ListNode* left, ListNode* right) {
        if (left == nullptr) {
            return right;
        }
        if (right == nullptr) {
            return left;
        }
        ListNode* res;
        if (left->val <= right->val) {
            res = left;
            left = left->next;
        } else {
            res = right;
            right = right->next;
        }
        ListNode* node = res;
        while (left != nullptr || right != nullptr) {
            if (left == nullptr) {
                node->next = right;
                right = right->next;
            } else if (right == nullptr) {
                node->next = left;
                left = left->next;
            } else {
                if (left->val <= right->val) {
                    node->next = left;
                    left = left->next;
                } else {
                    node->next = right;
                    right = right->next;
                }
            }
            node = node->next;
        }
        return res;
    }
};

This site is open source. Improve this page.