题目的主要信息:

  • 给定k个排好序的升序链表
  • 将这k个链表合并成一个大的升序链表,并返回这个升序链表的头

方法一:优先队列(小顶堆)

具体做法:

如果是两个有序链表合并,我们可能会利用归并排序合并阶段的思想:准备双指针分别放在两个链表头,每次取出较小的一个元素加入新的大链表,将其指针后移,继续比较,这样我们出去的都是最小的元素,自然就完成了排序。

其实这道题我们也可以两两比较啊,只要遍历链表数组,取出开头的两个链表,按照上述思路合并,然后新链表再与后一个继续合并,如此循环,知道全部合并完成。但是,这样太浪费时间了。我们就不能准备k个指针,每次比较得出k个指针的最小值吗?

答案是可以的!利用SLT提供的优先队列。优先队列是SLT提供的容器,它参照了堆排序,容器中的元素是有序的,如果是小顶堆,顶部元素就是最小的,每次可以直接取出最小的元素,而每次插入的成本根据堆排序,就是O(log2n)O(log_2n)。也就是每次该容器中有k个元素,我们可以直接拿出最小的元素,再插入下一个元素,相当于每次都是链表的k个指针在比较大小。

  • step 1:因为SLT提供的优先队列不能直接比较链表值的大小,因此我们要构造一个比较链表值大小的小顶堆,需要重载比较方式。
  • step 2:先遍历k个链表头,将不是空节点的节点加入优先队列。
  • step 3:每次依次弹出优先队列中的最小元素,将其连接子啊合并后的链表后面,然后将这个节点在原本链表中的后一个节点(如果不为空的话)加入队列,类似上述双指针的过程。
class Solution {
public:
    struct cmp {
    bool operator()(ListNode* a, ListNode* b) { //重载小顶堆比较方式
        return  a->val > b->val;  
    }
};
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq; //小顶堆
        for(int i = 0; i < lists.size(); i++){ //遍历所有链表第一个元素
            if(lists[i] != NULL) //不为空则加入小顶堆
                pq.push(lists[i]);
        }
        ListNode* res = new ListNode(-1); //加一个表头
        ListNode* head = res;
        while(!pq.empty()){ //直到小顶堆为空
            ListNode* temp = pq.top(); //取出最小的元素
            pq.pop();
            head->next = temp; //连接
            head = head->next;
            if(temp->next != NULL) //每次取出链表的后一个元素加入小顶堆
                pq.push(temp->next);
        }
        return res->next;
    }
};

复杂度分析:

  • 时间复杂度:O(nlog2k)O(nlog_2k),其中nn为所有链表的总节点数,最坏需要遍历所有的节点,每次加入优先队列排序需要O(log2k)O(log_2k)
  • 空间复杂度:O(k)O(k),优先队列的大小不会超过kk

方法二:归并排序思想

具体做法:

既然都是归并排序的思想了,那我们可不可以直接归并的分治来做,而不是顺序遍历合并链表呢?答案也是可以的!

归并排序是什么?简单来说就是将一个数组每次划分成等长的两部分,对两部分进行排序即是子问题。对子问题继续划分,直到子问题只有1个元素。还原的时候呢,将每个子问题和它相邻的另一个子问题利用上述双指针的方式,1个与1个合并成2个,2个与2个合并成4个,因为这每个单独的子问题合并好的都是有序的,直到合并成原本长度的数组。

我们这k个链表,就相当于上述合并阶段的k个子问题,需要两个合并,不断往上,最终合并成完整的一个链表。从链表数组的首和尾开始,每次划分从中间开始划分,划分成两半,将这两半子问题合并好了就成了两个有序链表,最后将这两个有序链表合并就成了,依据子问题递归处理:

  • 终止条件: 划分的时候直到左右区间相等或事左边大于右边。
  • 返回值: 每级返回已经合并好的子问题链表。
  • 本级任务: 对半划分,将划分后的子问题合并成新的链表。

合并过程如下所示:

alt

class Solution {
public:
    ListNode* Merge2(ListNode* pHead1, ListNode* pHead2) { //两个有序链表合并
        if(pHead1 == NULL) //一个已经为空了,直接返回另一个
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        ListNode* head = new ListNode(0); //加一个表头
        ListNode* cur = head;
        while(pHead1 && pHead2){ //两个链表都要不为空
            if(pHead1->val <= pHead2->val){ //取较小值的结点
                cur->next = pHead1;
                pHead1 = pHead1->next; //只移动取值的指针
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next; //只移动取值的指针
            }
            cur = cur->next; //指针后移
        }
        if(pHead1) //哪个链表还有剩,直接连在后面
            cur->next = pHead1;
        else
            cur->next = pHead2;
        return head->next; //返回值去掉表头
    }
    
    ListNode* divideMerge(vector<ListNode *> &lists, int left, int right){ //划分合并区间
        if(left > right) 
            return NULL;
        else if(left == right) //中间一个的情况
            return lists[left];
        int mid = (left + right) / 2; //从中间分成两段,再将合并好的两段合并
        return Merge2(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return divideMerge(lists, 0, lists.size() - 1); //k个链表归并排序
    }
};

复杂度分析:

  • 时间复杂度:O(nk)O(n*k),其中nn为所有链表的总节点数,最坏情况下每次合并都是O(n)O(n),分治为二叉树型递归,每个节点都要使用一次合并,需要合并k1k-1
  • 空间复杂度:O(log2k)O(log_2k),最坏情况下递归log2klog_2k层,需要log2klog_2k的递归栈