美文网首页
有序链表&&有序数组合并问题

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

作者: juexin | 来源:发表于2017-04-18 15:58 被阅读0次

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

    相关文章

      网友评论

          本文标题:有序链表&&有序数组合并问题

          本文链接:https://www.haomeiwen.com/subject/emlfzttx.html