有序链表&&有序数组合并问题

**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;
    }
};