美文网首页
21. Merge Two Sorted Lists

21. Merge Two Sorted Lists

作者: i_Eloise | 来源:发表于2018-01-21 09:58 被阅读0次
  • first attempt
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* begin,* end;
        if(l1==nullptr)
            return l2;
        if(l2==nullptr)
            return l1;
        if(l1->val<l2->val)
        {
            begin = l1;
            end = l1;
            l1=l1->next;
            end->next = nullptr;
        }
        else 
        {
            begin = l2;
            end = l2;
            l2=l2->next;
            end->next = nullptr;
         }
        while(l1!=nullptr && l2!=nullptr)
        {
            if(l1->val < l2->val)
            {
                end ->next = l1;
                end = end->next;
                l1=l1->next;
                end->next = nullptr;
            }
            else
            {
                end->next = l2;
                end = end->next;
                l2=l2->next;
                end->next = nullptr;
            }
        }
        if(l1==nullptr)
            end->next = l2;
        else
            end->next = l1;
        
        return begin;
    }
};
  • improved
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {   
    if(l1==nullptr)
        return l2;
    if(l2==nullptr)
        return l1;
    if(l1->val < l2->val)
    {
        ListNode * tmp = l1;
        tmp->next = mergeTwoLists(l1->next,l2);
        return tmp;
     }
    else 
    {
        ListNode * tmp = l2;
        tmp->next = mergeTwoLists(l1,l2->next);
        return tmp;
    }
        
    }
};
  • 2nd improved
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {   
    ListNode* prehead = new ListNode(-1);
        ListNode* prev = prehead;
        while(l1!=nullptr && l2!=nullptr)
        {
            if(l1->val < l2->val)
            {
                prev->next = l1;
                l1=l1->next;
            }
            else{
                prev->next = l2;
                l2=l2->next;
            }
            prev=prev->next;
        }
        prev->next = (l1==nullptr?l2:l1);
        return prehead->next;
        
    }
};

相关文章

网友评论

      本文标题:21. Merge Two Sorted Lists

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