题解 | #合并k个已排序的链表#

一.题目描述

NC51合并k个已排序的链表

合并k个已排序的链表并将其作为一个已排序的链表返回。

二.思路整理

我们可以想到一种最朴素的方法：用一个变量ans来维护以及合并的链表，第i次循环把第i个链表和ans合并，答案保存到ans中。 对于合并两个链表我们可以这样操作实现：首先创建一个空的链表头，将两个链表的头结点进行比较，小的那个直接插入空的表头后，同时，指针分别指向链表的的头结点或头结点的下一个节点，当两个链表进行比较的元素都不为空的话，依次从下到大连接，若有一个链表中比较的节点开始为空时，则将另一个链表的剩余节点添加到合并链表的末尾，其实总结的来说就是比较当前两个节点的较小节点未插入新的空节点后，从而实现两个有序链表的有序合并。

尾插法的实现：

List TailCreatList() //尾插法建立链表
{
	List L = (List)malloc(sizeof(PtrToNode));   //初始化空表，申请一个头结点
	L->Next = NULL;        //头指针为空
	List last = L;     //last为指向尾结点的指针
	for (int i = 0; i < 2; i++)
	{
		List p = (List)malloc(sizeof(struct Node));  //p指向新申请的结点
		cin >> p->Data;
		last->Next = p;
		last = p;  //last指向尾结点
	}
	last->Next = NULL;

	return L;
}

三.代码实现

class Solution {
public:
    //对两个链表进行合并
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a)||(!b)) return a? a : b;
        ListNode head(0), *r=&head;//r是链表插入的尾指针
        ListNode *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {//利用尾插法把数值小的插入
                r->next=aPtr;
                aPtr=aPtr->next;
            } else {
                r->next=bPtr;
                bPtr=bPtr->next;
            }
            r=r->next;
        }
        r->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }
    //遍历对第i个链表进行合并
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

时间复杂度：$O(n\ast n)O(n*n)$

空间复杂度：$O(n)O(n)$ 需要额外空间