Brief explanation, recursive and iterative solutions, C++


  • 0
    V

    Suppose, you have two sorted lists: A and B.
    So, we can consider 3 cases:

    • A is longer than B
    • B is longer than A
    • Both have the same length

    In result, you have to pass through all elements of the smallest list and then you can just merge the rest of another list.

    I've implemented this idea using an iterative and recursive approaches:

    • Recursive version:
    /**
    * 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||!l2)
               return l1?l1:l2;
           else if(l1->val>=l2->val){
               l2->next=mergeTwoLists(l1,l2->next);
               return l2;
           }
           l1->next=mergeTwoLists(l1->next,l2);
           return l1;
       }
    };
    
    
    • An iterative version:
    /**
     * 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||!l2)
                return l1?l1:l2;
            ListNode* head=new ListNode(0);
            ListNode* node=head;
            while(l1 && l2){
                if(l1->val<l2->val){
                    node->next=l1;
                    l1=l1->next;
                }
                else{
                    node->next=l2;
                    l2=l2->next;
                }
                node=node->next;
            }
            //
            node->next=l1?l1:l2;
            return head->next;
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.