LeetCode 23. 合并K个排序链表(两两合并)
原题链接
困难
作者:
米兰小铁匠y
,
2021-08-30 12:37:48
,
所有人可见
,
阅读 206
思路:从第一个链表开始逐一与后面的链表合并
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans=nullptr;
for(auto l:lists)
ans=merge(ans,l);
return ans;
}
ListNode* merge(ListNode *l1,ListNode *l2)
{
ListNode *res=new ListNode(-1);
ListNode *cur=res;
while(l1 && l2)
{
if(l1->val<l2->val)
{
cur=cur->next=l1;
l1=l1->next;
}
else
{
cur=cur->next=l2;
l2=l2->next;
}
}
while(l1)
{
cur=cur->next=l1;
l1=l1->next;
}
while(l2)
{
cur=cur->next=l2;
l2=l2->next;
}
return res->next;
}
};