题目描述
blablabla
样例
blablabla
算法1
二路归并
时间复杂度
参考文献
C++ 代码
ListNode* merge(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1);
auto cur = dummy;
while(l1 != NULL && l2 !=NULL)
{
if(l1->val > l2->val)
{
cur->next = l2;
l2 = l2->next;
}
else
{
cur->next = l1;
l1 = l1->next;
}
cur = cur->next;
}
cur->next = l1 !=NULL ? l1:l2;
return dummy->next;
}
合并k个排序链表
blablabla
时间复杂度
参考文献
C++ 代码
合并k个也是归并,然后新建节点,
ListNode* mergeKLists(vector<ListNode*>& lists) {
return mergeKLists(lists,0,lists.size()-1);
}
ListNode* mergeKLists(vector<ListNode*>& lists,int begin,int end)
{
if (end < begin) return NULL;
if (end == begin)
return lists[begin];
int mid = (begin+end) / 2;
auto p1 = mergeKLists(lists,begin,mid);
auto p2 = mergeKLists(lists,mid+1,end);
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (p1&&p2)
{
if(p1->val > p2->val)
{
cur->next = p2;
p2 = p2->next;
}
else
{
cur->next = p1;
p1 = p1->next;
}
cur = cur->next;
}
if(p1)
cur->next = p1;
else if(p2)
cur->next = p2;
return dummy->next;
}