ink plus 加个employee card 送 5k点么？# Money - 海外理财
W*e
1 楼
我的办法就是进行二分，将k个链表分为两个一组，组内进行merge。形成一个新的链表
集合。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链
表。这里用的辅助函数是mergeSortedList，合并两个有序链表，这个辅助函数复杂度
应该是O(n)。
我觉得这个算法的总时间复杂度是O(nlogK),大家觉得对吗？？
class Solution {
public:
ListNode* mergeSortedList(ListNode*l1,ListNode*l2)
{
ListNode *h1=l1,*h2=l2;
ListNode *newHead=new ListNode(0),*dummy=newHead; //newHead要赋
值，否则没有next。如果是C语言的话可以申请stack的对象
if(l1==NULL&&l2==NULL)
return NULL;
while(h1!=NULL&&h2!=NULL)
{
if(h1->val>=h2->val)
{
dummy->next=h2;
dummy=h2;
h2=h2->next;
}
else
{
dummy->next=h1;
dummy=h1;
h1=h1->next;
}
}
if(h1==NULL)
dummy->next = h2;
else if(h2==NULL)
dummy->next= h1;
return newHead->next;
}
ListNode *mergeKLists(vector &lists) {
if(lists.size() == 0)
return NULL;
int curSize = lists.size();
while(curSize > 1) {
int halfSize = (1 + curSize) / 2;
//merge i,i + halfSize
for(int i = 0 ; i < halfSize && i + halfSize < curSize; ++i) {
ListNode *first = lists[i];
ListNode *second = lists[i + halfSize];
ListNode *result = mergeSortedList(first,second);
lists[i] = result;
}
//set curSize to halfsize
curSize = halfSize;
}
return lists[0];
}
};
集合。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链
表。这里用的辅助函数是mergeSortedList，合并两个有序链表，这个辅助函数复杂度
应该是O(n)。
我觉得这个算法的总时间复杂度是O(nlogK),大家觉得对吗？？
class Solution {
public:
ListNode* mergeSortedList(ListNode*l1,ListNode*l2)
{
ListNode *h1=l1,*h2=l2;
ListNode *newHead=new ListNode(0),*dummy=newHead; //newHead要赋
值，否则没有next。如果是C语言的话可以申请stack的对象
if(l1==NULL&&l2==NULL)
return NULL;
while(h1!=NULL&&h2!=NULL)
{
if(h1->val>=h2->val)
{
dummy->next=h2;
dummy=h2;
h2=h2->next;
}
else
{
dummy->next=h1;
dummy=h1;
h1=h1->next;
}
}
if(h1==NULL)
dummy->next = h2;
else if(h2==NULL)
dummy->next= h1;
return newHead->next;
}
ListNode *mergeKLists(vector
if(lists.size() == 0)
return NULL;
int curSize = lists.size();
while(curSize > 1) {
int halfSize = (1 + curSize) / 2;
//merge i,i + halfSize
for(int i = 0 ; i < halfSize && i + halfSize < curSize; ++i) {
ListNode *first = lists[i];
ListNode *second = lists[i + halfSize];
ListNode *result = mergeSortedList(first,second);
lists[i] = result;
}
//set curSize to halfsize
curSize = halfSize;
}
return lists[0];
}
};
