合并K个排序链表 shuitang

题目

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

解法

我使用的解法便是使用堆来做。思路大概就是维护一个ListNode*小顶堆,然后每次取出堆顶的元素,插入到结果链表中,并把堆顶元素的 *next 进入堆中。时间复杂度为 $O(kn \times log k)$, 空间复杂度为$O(kn \times logk)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 struct CMP{
     bool operator()(const ListNode* a, const ListNode* b){
         return a->val >= b->val;
     }
 };
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        priority_queue<ListNode*,vector<ListNode*>,CMP> q;
        for(int i=0;i<lists.size();i++){
            if(lists[i])
            q.push(lists[i]);
        }
        ListNode* cur = new ListNode(-1);
        ListNode* head = cur;
        while(!q.empty()){
            ListNode* p = q.top();
            q.pop();
            ListNode* now = new ListNode(p->val);
            cur->next = now;
            cur = cur->next;
            if(p->next) q.push(p->next);
        }
        ListNode* p = head->next;
        delete head;
        return p;
    }
};

看了官方解答后,有一种分治的思想,值得学习。该方法采用了归并排序里使用的分治的思想来解决。下面图片也是来自官方解答:

img

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
         //官方解答这里写得确实不错
        if ((!a) || (!b)) return a ? a : b;
        //官方解答这里写得确实不错
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) { //官方解答这里写得确实不错
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
         //官方解答这里写得确实不错
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

于此,解决这类题的思路又多了一种了!