23.Merge k Sorted Lists¶

23.Merge k Sorted Lists¶

Tags: Hard Linked List Divide and Conquer Heap

Links: https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        return mergeList(lists, 0, lists.size() - 1);
    }

    ListNode * mergeList(vector<ListNode*> & lists, int left, int right) {
        if (left == right) return lists[left];
        if (right - left == 1) return mergeList(lists[left], lists[right]);

        int mid = left + ((right - left) >> 1);
        ListNode * leftNode = mergeList(lists, left, mid);
        ListNode * rightNode = mergeList(lists, mid + 1, right);

        return mergeList(leftNode, rightNode);
    }

    //合并两个有序链表
    ListNode * mergeList(ListNode* l1, ListNode* l2) {
        ListNode * dummy = new ListNode(0);
        ListNode *p = dummy;
        while (l1 && l2) {
            if (l1 -> val < l2 -> val) {
                p -> next = l1;
                p = p -> next;
                l1 = l1 -> next;
            }
            else {
                p -> next = l2;
                p = p -> next;
                l2 = l2 -> next;
            }
        }
        p -> next = (l1 ? l1 : l2);

        return dummy -> next;
    }
};

Runtime: 24 ms, faster than 91.08% of C++ online submissions for Merge k Sorted Lists.
Memory Usage: 20.5 MB, less than 5.95% of C++ online submissions for Merge k Sorted Lists.

思路很直接，多个链分成规模更小的子问题来求解，如果分解到最后只有一个链，直接返回，两个链就执行一下两个链的合并。多于两个链就执行分治。细节注意一下可能传入的数组为空。

这种解法利用了**最小堆**这种数据结构，首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后每次取出最小的那个元素加入最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时k个链表也合并为了一个链表，返回首节点即可.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        auto cmp = [](ListNode *l1, ListNode *l2){
            return l1 -> val > l2 -> val;
        };

        int n = lists.size();
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

        for (auto & e : lists) 
            if (e) pq.push(e);

        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (!pq.empty()) {
            ListNode *tmp = pq.top(); pq.pop();
            cur -> next = tmp;
            cur = cur -> next;
            if (cur -> next) pq.push(cur -> next);
        }
        return dummy -> next;
    }
};