难度:hard
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题解：题目直接翻译过来就是 mergersort一共k个链表 那么既然它题目已经给出了mergesort的这个提示 那么用merge来排序就不会超过时间复杂度
主要考虑还是要用分治法来做这道题 如果一开始就对整个vector进行操作 那么代码量大 并且也没有体现到分治法的一个思想 于是我先写了一个merge两个ListNode的函数 然后在lists容器的size大于1时 始终对vector的第0个和第1个元素进行merge 将得到的链表压入容器尾部 最后容器的size变为1 这个元素就是我们merge了k个链表得到的独个链表
代码如下：
ListNode* mergeSort(ListNode *l1,ListNode *l2) { if(l1==NULL&&l2!=NULL) return l2; else if(l2==NULL&&l1!=NULL) return l1; else if(l1==NULL&&l2==NULL) return NULL; int x=0; if(l1->val>=l2->val) {x=l2->val;l2=l2->next;} else {x=l1->val;l1=l1->next;} ListNode *result=new ListNode(x); ListNode *head=new ListNode(0); head=result; while(1){ if(l1==NULL) { if(l2==NULL) break; else if(l2!=NULL) { head->next=l2; l2=l2->next; head=head->next; } } else if(l2==NULL) { head->next=l1; l1=l1->next; head=head->next; } else{ if(l1->val>=l2->val) { head->next=l2; l2=l2->next; head=head->next; } else{ head->next=l1; l1=l1->next; head=head->next; } } } return result; } ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()==0) return NULL; else if(lists.size()==1&&lists[0]==NULL) return NULL; while(1) { if(lists.size()==1) break; else{ ListNode *p=new ListNode(0); p=mergeSort(lists[0],lists[1]); lists.push_back(p); lists.erase(lists.begin()); lists.erase(lists.begin()); } } return lists[0]; } 一开始没用这个方法而是直接对所有元素进行处理的时候 好像是会Error 空间超出限制 非常迷茫 本来查了一个free函数用来释放空间 包含在C语言的.h文件 后来一交过了 所以现在用的这个方法估计不止时间复杂度满足条件 空间复杂度也满足条件