**21. Merge Two Sorted Lists **
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
代码如下:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode* newhead = new ListNode(-1);
ListNode* last = newhead;
while(l1&&l2)
{
if(l1->val<l2->val)
{
last->next = l1;
l1 = l1->next;
}
else
{
last->next = l2;
l2 = l2->next;
}
last = last->next;
}
if(l1==NULL)
last->next = l2;
else if(l2==NULL)
last->next = l1;
return newhead->next;
}
};
**23. Merge k Sorted Lists **
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
ListNode* list = NULL;
if(n==0)
return list;
for(int i=0;i<n;i++)
{
list = merge(list,lists[i]);
}
return list;
}
ListNode* merge(ListNode* l1,ListNode* l2)
{
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode* newhead = new ListNode(-1);
ListNode* last = newhead;
while(l1&&l2)
{
if(l1->val<l2->val)
{
last->next = l1;
l1 = l1->next;
}
else
{
last->next = l2;
l2 = l2->next;
}
last = last->next;
}
if(l1==NULL)
last->next = l2;
else if(l2==NULL)
last->next = l1;
return newhead->next;
}
};
**88. Merge Sorted Array **
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m-1,j = n-1,k = m+n-1;
if(nums1.size()<(m+n))
return;
while(i>=0&&j>=0)
{
if(nums1[i]<nums2[j])
nums1[k] = nums2[j--];
else
nums1[k] = nums1[i--];
k--;
}
if(j==-1)
{
while(k>=0)
nums1[k--] = nums1[i--];
}
else
{
while(k>=0)
nums1[k--] = nums2[j--];
}
return;
}
};
网友评论