题意概述

• 给定k个升序的链表
• 要求将其合为一个升序的链表

方法一：顺序合并

思路与具体做法

• 依次合并两个链表
• 每次合并在两个链表的公共部分，将权值较小的结点放在新建链表后
• 最后如果两个链表谁还有剩余，则接在新建链表后，即完成对两个链表的合并
• 如此进行k次，即完成k个链表的合并

class Solution {
public:
	ListNode* merge(ListNode* p,ListNode* q){
		if(!p||!q)return !q?p:q;//如一个链表为空，则直接返回另外一个 
		ListNode *head=new ListNode(0),*s=head;//新建链表，及其头指针 
		while(p&&q){//在两个链表的公共部分，将权值较小的结点放在新建链表后 
			if(p->val<q->val){
				s->next=p;
				p=p->next;
			}else{
				s->next=q;
				q=q->next;				
			}
			s=s->next;//指针后移 
		}
		if(p)s->next=p;//如果两个链表谁还有剩余，则接在新建链表后 
		else s->next=q;
		return head->next;//返回排序后的链表 
	}
    ListNode *mergeKLists(vector<ListNode *> &lists) {
		ListNode* head=NULL; 
        for(int i=0;i<lists.size();i++){
        	head=merge(head,lists[i]);//依次将两个链表合并 
		}
		return head;//返回结果链表 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(k^2\ast n)O(k^2*n)$O(k2∗n)，依次合并两个链表，第i次合并耗时$O(i\ast n)O(i*n)$O(i∗n)，所以总的时间复杂度为$O({\sum }_{i=1}^{i=k}i\ast n)O(\backslash sum\_\{i=1\}^\{i=k\}\; i*n)$O(∑i=1i=k​i∗n)=$O\left(\right((1+k)\ast k/2)\ast n)O(((1+k)*k/2)*n)$O(((1+k)∗k/2)∗n)=$O(k^2\ast n)O(k^2*n)$O(k2∗n)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅新建了常数级别的指针，结点

方法二：优先队列

思路与具体做法

• 遍历所有结点，并将结点权值保存在按升序排列的优先队列里
• 之后从优先队列中取出元素新建链表即可

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
    	priority_queue<int,vector<int>,greater<int> >q;//从小到大排序的优先队列 
        for(int i=0;i<lists.size();i++){
        	ListNode* t=lists[i];//取出头结点 
        	while(t){//遍历链表并保存结点权值 
        		q.push(t->val);
        		t=t->next; 
			}
		} 
		ListNode* head=new ListNode(0);//新建链表 
		ListNode* p=head;//头指针 
		while(!q.empty()){
			p->next=new ListNode(q.top());q.pop();//从优先队列中取出元素新建链表  
			p=p->next;//指针后移 
		}
		return head->next;//返回结果链表 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n{2}_{}n\right)O(n\backslash log\_\{2\}\{n\}\; )$O(nlog2​n)，保存结点权值和取出结点权值新建链表各遍历了n个结点，每个结点的插入删除时间复杂度是$O\left(2_{}n\right)O(\backslash log\_\{2\}\{n\}\; )$O(log2​n)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，优先队列总共保存了n个结点