[BSSD]回国一趟回来做题很难进入状态了,顺便问下那个Merge k Sorted# JobHunting - 待字闺中
a*e
1 楼
回国一趟回来做题很难进入状态了
Merge k sorted linked lists and return it as one sorted list. Analyze and
describe its complexity.
有人面试碰到这题么?我洋洋洒洒写了很多代码,OJ说Time Limit Exceeded
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
int n = lists.size();
if (n==0) return NULL;
ListNode *ret = lists[0];
for (int i=1; i {
ret = merge2Lists(ret, lists[i]);
}
return ret;
}
private:
ListNode *merge2Lists(ListNode *a, ListNode *b)
{
if (a==NULL&&b==NULL) return NULL;
ListNode *r=NULL, *prev=NULL;
if (a==NULL&&b!=NULL) return b;
if (a!=NULL&&b==NULL) return a;
ListNode dummy(-1);
dummy.next = a->val>b->val?b:a;
prev = dummy.next;
if (dummy.next==a)
a= a->next;
else
b=b->next;
while(a!=NULL&&b!=NULL)
{
if (a->valval)
{
prev->next = a;
prev = a;
a=a->next;
}
else
{
prev->next=b;
prev = b;
b=b->next;
}
}
prev->next = a!=NULL?a:b;
return dummy.next;
}
Merge k sorted linked lists and return it as one sorted list. Analyze and
describe its complexity.
有人面试碰到这题么?我洋洋洒洒写了很多代码,OJ说Time Limit Exceeded
class Solution {
public:
ListNode *mergeKLists(vector
int n = lists.size();
if (n==0) return NULL;
ListNode *ret = lists[0];
for (int i=1; i
ret = merge2Lists(ret, lists[i]);
}
return ret;
}
private:
ListNode *merge2Lists(ListNode *a, ListNode *b)
{
if (a==NULL&&b==NULL) return NULL;
ListNode *r=NULL, *prev=NULL;
if (a==NULL&&b!=NULL) return b;
if (a!=NULL&&b==NULL) return a;
ListNode dummy(-1);
dummy.next = a->val>b->val?b:a;
prev = dummy.next;
if (dummy.next==a)
a= a->next;
else
b=b->next;
while(a!=NULL&&b!=NULL)
{
if (a->val
{
prev->next = a;
prev = a;
a=a->next;
}
else
{
prev->next=b;
prev = b;
b=b->next;
}
}
prev->next = a!=NULL?a:b;
return dummy.next;
}