题目:
image.png
思路一:
暴力法:
每次以两个进行操作,合并完两个后形成的新链表继续与下一个进行合并,直到所有的都合并完.
image.png
不过时间复杂度相当高,指数级
这里不予实现,重点介绍后面两种思路
思路二:
排序法:
先将所有的链表节点放到一个vector中,然后整体对vector进行排序(stl的sort排序函数),最后将其连成一个链表;
image.png
这个较为容易想到,但是借助了stl,有些赖皮.
复杂度为:O(kN*logkN)
但是还是给出实现代码:
#include <vector>
#include <algorithm>
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//重载
bool cmp(const ListNode *a, const ListNode *b){
return a->val < b->val;
}
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
//创建连接所有节点的vector
std::vector<ListNode*> node_list;
//把所有的节点放到node_list中
for(int i=0;i<lists.size();i++){
//用一个head指针指向链表头节点
ListNode* head = lists[i];
//放入
while(head){
node_list.push_back(head);
head = head->next;
}
}
//判空
if(node_list.size() == 0){
return NULL;
}
//进行排序,三个参数,起始点,终止点,排序规则(以函数重载形式给出)
std::sort(node_list.begin(), node_list.end(), cmp);
//从1开始是保证不会遍历到空的***
for(int i=1; i<node_list.size(); i++){
node_list[i-1]->next = node_list[i];
}
//为了便于验证,最后一个节点之后接空
node_list[node_list.size()-1]->next = NULL;
return node_list[0];
}
};
思路三:
分治法
对k个链表进行分治,两两进行合并
image.png
复杂度为O(kNlogk)
其中还用到了T21的那个函数,采用递归思想,值得多看几遍!
#include <vector>
#include <algorithm>
/**
* 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 NULL;
}
//只有一个链表用不了分治法
if(lists.size() == 1){
return lists[0];
}
//只有两个链表就只用直接调用
if(lists.size() == 2){
return mergeTwoLists(lists[0],lists[1]);
}
//确定中间数
int mid = lists.size()/2;
//拆分lists为两个子lists
std::vector<ListNode *> sub_lists1;
std::vector<ListNode *> sub_lists2;
for(int i = 0; i < mid; i++){
sub_lists1.push_back(lists[i]);
}
for(int i = mid; i < lists.size(); i++){
sub_lists2.push_back(lists[i]);
}
//分治
ListNode *l1 = mergeKLists(sub_lists1);
ListNode *l2 = mergeKLists(sub_lists2);
//return反映递归思想
return mergeTwoLists(l1,l2);
}
//这里需要用到T21的方法
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode tem_head(0);
ListNode *ptr = &tem_head;
while(l1&&l2){
//如果l1小
if(l1->val <= l2->val){
ptr->next = l1;
//l1向后移动一位
l1 = l1->next;
}else{
ptr->next = l2;
//l2向后移动一位
l2 = l2->next;
}
//指向新连接的节点
ptr = ptr->next;
}
//不用考虑tem中有无值得情况,直接将剩余的接上去,都是一样的
if(l1){
//剩下的都是大于tem中的数
ptr->next=l1;
}
if(l2){
//剩下的都是大于tem中的数
ptr->next=l2;
}
return tem_head.next;
}
};
总结:
今天完成的还不错,1个小时完成了任务,明天继续加油!
