LeetCode 23. 合并K个升序链表 (链表、堆、分治)

23. 合并K个升序链表

• 堆
  k路归并问题
  时间复杂度: O ( k n ∗ l o g ( k ) ) O(kn*log(k)) O(kn∗log(k))

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    struct Node{
        ListNode* p;
        Node(ListNode*p):p(p){}
        bool operator<(const Node& b) const{
            return p->val>b.p->val;
        } 
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* preHead = new ListNode; //哨兵
        ListNode* pre = preHead;
        priority_queue<Node> pq;
        for(int i=0;i<lists.size();i++){
            if(lists[i]) pq.push(Node(lists[i]));
        }
        while(pq.size()){
            Node node = pq.top();
            pq.pop();
            pre->next = node.p;
            pre = pre->next;
            if(node.p->next){
                pq.push(Node(node.p->next));
            }
        }
        return preHead->next;
    }
};

• 分治算法
  如果两两合并的话，时间复杂度： O ( k 2 ∗ n ) O(k^2*n) O(k2∗n)

分治的话：一次合并区间的一半。就像是归并排序一样。
时间复杂度： O ( k ∗ l o g ( k ) ∗ n ) O(k*log(k)*n) O(k∗log(k)∗n)

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

    ListNode* devide_conquer(vector<ListNode*>& lists,int l,int r){
        if(l==r) return lists[l];
        if(l>r) return nullptr;
        int mid = l+(r-l)/2;
        ListNode* left = devide_conquer(lists,l,mid);
        ListNode* right = devide_conquer(lists,mid+1,r);
        return mergeTwoLists(left,right);
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode; // 哨兵
        ListNode* pre = preHead;  // 移动的哨兵
        while(l1 && l2){
            if(l1->val<l2->val){
                pre->next = l1;
                l1 = l1->next;
            }else{
                pre->next = l2;
                l2 = l2->next;
            }
            pre = pre->next;
        }
        pre->next = (l1?l1:l2);
        return preHead->next;
    }
};