题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
思路讲一下, 由于这个题目很坑爹, 时间复杂度要达到nlogn, 那么意味着我们不能用双循环, 就很恶心, 所以我们分解题目步骤, 思路如下:
- 先让列表全部串起来, 形成一个未排序的大链表
- 然后把链表排个序, 返回头结点即可
注意要点
- 由于牛客网给的输入并不是C++标准库里的链表list而是指针, 那么我们需要自己手动给链表排序
- 排序算法有很多, 但是冒泡等排序方法复杂度太高, 我们选择插入的时候自动按顺序排序, 这样复杂度就只有O(n)
- 方法的话可以用C++标准库里的multiset, 他可以给每个元素排序且每个数值可以存放多个, 避免冲突问题, 全部插入完成后再挨个赋值回去就行了
- 注意处理全空容器和只含有空链表的容器, 两个概念是不一样的比如前者是[], 后者是[{},{}]这样的
本人代码写的很丑, 也没采用模块化设计, 如果看不懂我代码的欢迎留言. 希望各位看官老爷不要嫌弃
/** * 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) { if (lists.empty() == true) {//如果是空就返回空 return NULL; } ListNode* temp, *initList; vector<ListNode*> endList;//endList代表一个临时用于操作lists的相同的vector(容器, 也就是存放多链表的东西), 等于说我们复制一份进行瞎搞操作, 不会影响原有的容器 int counterNb = 0;//计数器, 用于计数和计算链表或者容器长度/容量 for (vector<ListNode*>::iterator it = lists.begin(); it != lists.end(); it++) {//采用迭代器,把空链表全部删除 if (*it == NULL) { it = lists.erase(it); it--; } } if (lists.empty() == true) {//删完以后如果是空vector(容器, 也就是存放多链表的东西), 则直接返回空 return NULL; } endList = lists;//进行复制lists操作 temp = endList[0];//让temp指针指向容器的第一个节点作为头结点, 等一下可以移动temp来达成我们想要的操作 initList = temp;//专门搞个头结点指针用于记录 counterNb = 0;//初始化计数器, 此时计数器用来操作第x个链表 while (endList[counterNb] != NULL) {//由于条件太苛刻, 我们这一轮负责把每个链表都串起来 if (endList[counterNb]->next != NULL) { endList[counterNb] = endList[counterNb]->next;//对于单个链表来说, 如果下个节点不为空则移动到下个节点 } else {//下个节点为空 if (counterNb < lists.size() - 1) {//如果没到最后一个链表 endList[counterNb]->next = endList[counterNb + 1];//那么我们就让他指向下一个链表的头结点 endList[counterNb] = endList[counterNb]->next;//移动到下一个节点 counterNb++; } else {//到了最后一个链表也让他进入下一个节点-空节点, 用于跳出循环 endList[counterNb] = endList[counterNb]->next;//移动到下一个节点 } } } temp = initList;//临时指针恢复到头结点位置 counterNb = 0;//初始化计数器, 此时用来计算链表长度, 其实不需要, 因为我们可以用C++标准库里的迭代器 while (temp != NULL) { temp = temp->next; counterNb++; } temp = initList;//临时指针恢复到头结点位置 multiset<int> tempSet;//直接使用multiset可以帮忙排序, 也兼容多个重复的值 for (int i = 0; i < counterNb; i++) {//把值全部插入到multiset中, 它会自动帮我们升序排序 tempSet.insert(temp->val); temp = temp->next; } temp = initList;//临时指针恢复到头结点位置 for (multiset<int>::iterator it = tempSet.begin(); it != tempSet.end(); it++) { temp->val = *it;//挨个重新覆写数值到原有的链表 temp = temp->next; } return initList;//把头结点传回去就好啦 } };