题目

Merge K Sorted Lists

思路

除了暴力求解，这道题有两条思路：利用最小堆和分而治之思想。

最小堆求解

由于这道题是将k个链表合并，并且这些链表都已经是有序的链表了，直觉告诉我们肯定是依次取它们的头节点进行比较，然后按从小到大的次序插入到新的头节点中。

那么堆结构就能够满足这样的需求，首先将k个链表的头节点构建成一个堆结构，然后自下而上地调整这样的堆使得最小的一个值在根节点，此时取出那个根节点作为第一个最小值节点。

那么剩下要做的就是给这个被破坏的堆重新增加一个节点，这时又要考虑两种情况：一种是当k个链表的节点都已经是堆中的节点时，那么被拿去的根节点就需要用最后的叶子节点来更换；另一种是K个链表的节点还没有初次遍历完，那么直接将新遍历到的节点换上被拿去的根节点。然后自上而下调整堆结构就好。

最小堆的构建依照完全二叉树的特性，可以使用2倍关系找到其父节点或孩子节点。一开始自下而上调整，从最后一个父节点开始调整，具体实现可以看一下的代码。

时间复杂度O(nk*logk) 空间复杂度O(k)

代码

Class Solution{
public:
    void makeHeap(vector<ListNode*> &heap){
        int para_last = (heap.size()-1)/2;
        for (int i = para_last; i >= 0  ; i--){
            minHeap(heap, i);
        }
    }

    void minHeap(vector<ListNode*> &heap, int i){
        int left = 2*i; // 找到父节点i的子节点
        int right = left + 1;
        int least = i;   // 假设最小值节点为i

        //得到最小值所在的vector索引
        if(left < heap.size() && heap[left]->val < heap[i]->val)
            least = left;
        if(right < heap.size() && heap[right]->val < heap[least]->val)
            least = right;

        if(least!=i){
            swap(heap[i],heap[least]);
            minHeap(heap, least);// 如果该交换打乱了下面的顺序，那就要继续为以下的进行堆排序。
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        if(lists.empty()) return NULL;
        vector<ListNode*> heap;//最小堆
        ListNode *result = new ListNode(0);

        //将每个链表的头节点插入heap
        for (int i = 0; i < lists.size(); ++i){
            if(lists[i]!=NULL)
                heap.push_back(lists[i]);
        }

        makeHeap(heap);//建立初始的最小堆
        ListNode *p = result;
        while(!heap.empty()){
            // 将堆顶插入到p中
            ListNode *top = heap[0];
            cout<<top->val<<endl;
            p -> next = top;
            p = p -> next;

            ListNode* next = top -> next;
            if(next!=NULL){
                //如果该链表还有元素，那就将其接上堆顶
                heap[0] = next;
            }else{
                //如果该链表没有元素，那就将堆最后的一个元素插入堆顶
                swap(heap[0],heap[heap.size()-1]);
                //并删除堆中最后一个元素
                heap.pop_back();
            }
            //重新调整堆
            minHeap(heap,0);
        }
        return result -> next;
    }
}

分而治之思想

想到分而治之思想的话就可以利用leetcode21的题解做分的操作，然后只需要在mergerK里面写上合的步骤。一开始需要设置一个结尾的指针，用来监控分治的进度，需要考虑的是，什么时候分治停止。

停止就是当这个结尾指针等于0的时候，那么只要该结尾指针还大于0，就需要不断分治，例如两个链表a和b，通过merge2算法得到新链表并赋值给a，这样a就更长了。依次类推不断分治，知道end为0。

时间复杂度O(nk*logk) 空间复杂度O(1)

代码

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;
       int end = lists.size()-1;//设置尾部指针
       while(end > 0){//当尾部指针还未到达0时，说明分支算法还未结束
            int begin = 0;
            while(begin < end){//当一波分治未结束时
                lists[begin] = mergeTwoLists(lists[begin],lists[end]);
                begin ++;
                end --;
            }
       }
       return lists[0];
    }

private:
    //该算法就是leetcode21的solution
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2; // list 1 is empty
        if (!l2) return l1; // list 2 is empty

        ListNode *dummy = new ListNode(0);
        ListNode *currentTail = dummy; // current tail of the new list
        while (l1 && l2){
            if (l1->val <= l2->val){
                currentTail->next = l1;
                currentTail = l1;
                if (l1->next)
                    l1 = l1->next;
                else{
                    l1->next = l2;
                    return dummy->next;
                    }
            }else {
                    currentTail->next = l2;
                    currentTail = l2;
                    if (l2->next)
                        l2 = l2->next;
                    else{
                        l2->next = l1;
                        return dummy->next;
                    }
            }
        }
    }
};