Efficient and clean iterative and recursive solutions in C++


  • 6

    Iterative

    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            int c = 0;
            ListNode newHead(0);
            ListNode *t = &newHead;
            while(c || l1 || l2)
            {
                c += (l1? l1->val : 0) + (l2? l2->val : 0);
                t->next = new ListNode(c%10);
                t = t->next;
                c /= 10;
                if(l1) l1 = l1->next;
                if(l2) l2 = l2->next;
            }
            return newHead.next;
        }
    };
    

    Recursive

    class Solution 
    {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            if(!l1 && !l2) return NULL;
            int c = (l1? l1->val:0) + (l2? l2->val:0);
            ListNode *newHead = new ListNode(c%10), *next = l1? l1->next:NULL;
            c /= 10;
            if(next) next->val += c;
            else if(c) next = new ListNode(c);
            newHead->next = addTwoNumbers(l2? l2->next:NULL, next);
            return newHead;
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    A

    How fast are they? Your first one is similar to mine but I got "better than 8%".


  • 0

    @alejandroerickson You should run them several times to make sure the stable time. Actually both of them once achieved 36ms but it's not the fact, the fact is that they are clean and efficient enough which I always pursue -> clean and efficient code.


  • 1
    A

    @LHearen huh... min in 20ms, after I applied your correction ^_^


  • 0

    @alejandroerickson Nice work, man! Have fun around!


  • 0
    J

    @LHearen that is a very clean way of handling it. Would you guide me in how to make mine work? I think it is almost there I'm just missing a little guidance. Here is what I have so far.

      ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            if(!l1 && !l2)return NULL;
            if(!l1)return l2;
            if(!l2)return l1;
            int rmd = 0;
            ListNode* tmp;
            
            while(!l1 || !l2){
                int count = l1->val + l2->val;
                
                if(count < 10){
                    if(rmd ==1){
                        tmp = new ListNode(count + rmd);
                        tmp->next = new ListNode(0);
                        tmp = tmp->next;
                        if(l1->next)l1 = l1->next;
                        if(l2->next)l2 = l2->next;
                        rmd = 0;
                    }else{
                        tmp = new ListNode(count);
                        tmp->next = new ListNode(0);
                        tmp = tmp->next;
                        if(l1->next)l1 = l1->next;
                        if(l2->next)l2 = l2->next;
                    }
                }else{
                    count = count%10;
                    tmp = new ListNode(count);
                    rmd = 1;
                    tmp->next = new ListNode(0);
                    tmp = tmp->next;
                    if(l1->next)l1 = l1->next;
                    if(l2->next)l2 = l2->next;
                }
            }return tmp;
        }
    

  • 0

    @jag028 Your solution is kind of redundant, dude. Perhaps you should read the solutions above and come up with a better one. B.T.W. your code should be formatted properly using backquotes ```.


  • 1
    J

    @LHearen cool, I appreciate your help. Thank you


  • 0
    A

    Hi @LHearen , thanks for the very clean explanation. I made a slight change to the iterative code, which I can see the correct results printed out, but eventually returns an empty linked list, could you help me to clear it?

    ListNode* addTwoList2(ListNode* l1, ListNode* l2) {
        int c = 0;
        
        ListNode* result;
        while(c || l1 || l2) {
            std::cout<<"print digit:  ";
            c += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
            result = new ListNode(c%10);
            std::cout<<result->val<<endl;
            c /= 10;
            result = result->next;
            if (l1)
                l1 = l1->next;
            if (l2)
                l2 = l2->next;
            
        }
        return result;
    }
    

    Here the "result" doesn't return anything, while the print out looks fine.

    Thanks!


  • 1

    @Alex.Wang.9 Your result move forward each time, you should use another temporary to do this (t = t->next) and retain the result value.


Log in to reply
 

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