Merge k Sorted Lists
LeetCode笔记 阅读(486)
编号 : 23 难度 : <font color="red">Hard</font> # 题目 : >Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. > >**Example**: >>**Input**: >>``` >>[ >> 1->4->5, >> 1->3->4, >> 2->6 >>] >>``` >>**Output**: 1->1->2->3->4->4->5->6 > # 解 : ```Cpp /** * 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) { ListNode preHead(0); // 为了方便,preHead.next指向返回链表的头节点 ListNode* pos = &preHead; // 指示链表的尾,方便添加节点 int k = lists.size(); while(true) { /* 查找剩余节点里最小的节点 */ ListNode** select = nullptr; // 采用二级指针,方便从移动 for(int i = 0; i < k; i++) { if((select == nullptr && lists[i] !=nullptr) || (select != nullptr && lists[i] !=nullptr && (*select)->val > lists[i]->val) ) { select = &lists[i]; } } if(select == nullptr) { // 所有链表的所有节点都已经遍历完了 break; } else { pos->next = *select; // 将找到的最小节点赋给pos->next *select =(*select)->next; // 将select向后移,本质上是将list[i]向后移,即删除该节点 pos = pos->next; } } return preHead.next; } }; ``` # 分析 : 这道题要求将`k`个升序的链表合并为一个。 上述解法创建一个新的链表,并从输入的各个链表的顶部挑选最的小节点,将该节点插入新链表并从原链表中移除,直到所有节点都处理完为止。 这个解法非常的慢,内层的`for`循环的时间复杂度是`O(k)`,其中`k`为输入的链表的个数。 外层的`while`循环每次处理一个节点,直到所有节点都处理完,复杂度为`O(n)`,其中`n`为节点总个数。 所以循环嵌套的总时间复杂度为`O(k*n)`,`k`为链表个数,`n`为节点总个数 ## 更快的办法 ```Cpp /** * 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) { map<int, int> buffer; // buffer保存各个值出现的次数 int k = lists.size(); if(k == 0) { return nullptr; } ListNode preHead(0); // 为了方便,preHead.next指向返回链表的头节点 ListNode* pos = &preHead; // 指示链表的尾,方便添加节点 /* 遍历各个节点,保存各个值出现的个数 */ for(int i = 0; i < k; i++) { for(ListNode* lp = lists[i]; lp != nullptr; lp = lp->next) { if(buffer.find(lp->val) == buffer.end()) { buffer[lp->val] = 1; } else { buffer[lp->val] += 1; } } } /* std::map是按key升序的 */ for(auto& pair : buffer) { /* 根据值出现的次数,相应的插入节点 */ for(int i = 0; i < pair.second; i++) { pos->next = new ListNode(pair.first); pos = pos->next; } } return preHead.next; } }; ``` 这个方法遍历全部节点(复杂度为`O(n)`,其中`n`是节点总个数)使用`std::map`保存所有节点中各个值出现的次数。 然后遍历该`map`(复杂度为`O(mlogm)`,其中`m`是值的种数`),根据各个值出现的次数插入相应数量的节点。 故总的复杂度为`O(n + mlogm)`,其中`n`是节点的总个数,`m`是值的种数。 > 这里利用到了`std::map`有序的特性,它的查找复杂度为`O(logn)`,`n`是元素个数。 ## 分治法 ```Cpp /** * 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.size() == 0) { return nullptr; } /* 分治 */ while(lists.size() > 1) { lists.push_back(mergeTwoLists(lists[0], lists[1])); lists.erase(lists.begin()); lists.erase(lists.begin()); } return lists[0]; } /* 合并两个链表 */ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode preHead(0); // 为了方便,preHead.next指向返回链表的头节点 ListNode* pos = &preHead; // 指示链表的尾,方便添加节点 while(l1 != nullptr || l2 != nullptr) if(l1 == nullptr) { pos->next = l2; l2 = nullptr; } else if(l2 == nullptr) { pos->next = l1; l1 = nullptr; } else if(l1->val < l2->val) { pos->next = new ListNode(l1->val); pos = pos->next; l1 = l1->next; } else { pos->next = new ListNode(l2->val); pos = pos->next; l2 = l2->next; } return preHead.next; } }; ``` 这个解法将输入的链表两两合并,直到最终合并为一个链表。 合并两个链表的方法和最开始合并`k`个的方法一样,所以合并两个链表的复杂度为`O(m)`,其中`m`是两个链表的元素总个数,`m <= n`,`n`为全部链表的元素总个数。 两两合并到最终成为一个链表需要合并`logk`次,故复杂度为`O(logk)`,其中`k`是输入链表的总个数。 故整个算法的时间复杂度为`O(nlogk)`,其中`n`为节点的总个数,`k`为链表的个数。 ## 效率对比 | 方案 | Runtime | Memory | | :-: | :-: | :-: | | O(k*n) | 460 ms | 10.7 MB | | O(n + mlogm) | 24 ms | 11.6 MB | | O(nlogk) | 264 ms | 16.3 MB | 从表中结果可以看出,测试集中,链表的总个数较多,但是出现的值的种数很少。