Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
60 lines (58 sloc) 1.38 KB
problem:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
--------------------------------------------------------------------------------------------------
solution:
//再强调一下指针的指针的用法
//思路是两两merge,一直合并直到为一时停止,时间复杂度O(nlogk),n为总长度, k为链表的个数
ListNode* mergeTwoLists(ListNode *head1, ListNode *head2)
{
if(head1 == NULL)
return head2;
else if(head2 == NULL)
return head1;
ListNode *proot = NULL;
ListNode **ptail = &proot;
while(head1 && head2)
{
ListNode *minNode;
if(head1->val < head2->val)
{
minNode = head1;
head1 = head1->next;
}
else
{
minNode = head2;
head2 = head2->next;
}
*ptail = minNode;
ptail = &(minNode->next);
}
ListNode *lremain = head1 ? head1 : head2;
while(lremain)
{
*ptail = lremain;
ptail = &(lremain->next);
lremain = lremain->next;
}
return proot;
}
ListNode *mergeKLists(vector<ListNode *>& lists)
{
if(lists.size() == 0)
return NULL;
int curSize = lists.size();
while(curSize > 1)
{
int halfSize = (1 + curSize) / 2;
for(int i = 0; i < halfSize && i + halfSize < curSize; i++)
{
ListNode *first = lists[i];
ListNode *second = lists[i + halfSize];
ListNode *result = mergeTwoLists(first, second);
lists[i] = result;
}
curSize = halfSize;
}
return lists[0];
}