Is this Algorithm optimal or what?


  • 273
    P
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode c1 = l1;
            ListNode c2 = l2;
            ListNode sentinel = new ListNode(0);
            ListNode d = sentinel;
            int sum = 0;
            while (c1 != null || c2 != null) {
                sum /= 10;
                if (c1 != null) {
                    sum += c1.val;
                    c1 = c1.next;
                }
                if (c2 != null) {
                    sum += c2.val;
                    c2 = c2.next;
                }
                d.next = new ListNode(sum % 10);
                d = d.next;
            }
            if (sum / 10 == 1)
                d.next = new ListNode(1);
            return sentinel.next;
        }
    }

  • 5
    R

    Thanks for your shared! From my perspective, your code is so compact and beautiful. It seems to be optimal in terms of space complexity.


  • 3
    M

    This code is fantastic, beautiful and simple.


  • 5
    W

    ListNode sentinel = new ListNode(0);
    Don't you need to delete it? I think it will be a memory leak.


  • 8

    The code is in Java. In C++ you will need to delete it.


  • 6
    S

    Carry can also be taken care in the loop:

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        
        int carry = (l1->val + l2->val) / 10;
        ListNode *l3 = new ListNode((l1->val + l2->val) % 10);
        ListNode *tail = l3;
        l1 = l1->next;
        l2 = l2->next;
        
        while(l1 || l2 || carry)
        {
            int sum = ((l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry);
            ListNode *t  = new ListNode(sum % 10);
            carry = sum / 10;                                          
    
            if(l1)
                l1 = l1->next;
            if(l2)
                l2 = l2->next;
            tail->next = t;
            tail = t;
        }
        
        return l3;
    }
    

  • 1
    2

    I think this is a ok solution, slightly more compact.

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode current = new ListNode(0);
            ListNode head = current;
            
            int shift = 0;
            do
            {
                current.val = ((l1!=null)?l1.val:0) + ((l2!=null)?l2.val:0) + shift;
                shift = current.val / 10;
                current.val%=10;
                l1 = (l1!=null)?l1.next:null;
                l2 = (l2!=null)?l2.next:null;
                if((l1==null)&&(l2==null)){break;}
                
                current.next = new ListNode(0);
                current = current.next;
            }while(l1!=null || l2!=null);
            if(shift>0){current.next = new ListNode(1);}
            return head;
        }
    

  • 0
    I
    This post is deleted!

  • 15
    N
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int left = 0;
            ListNode dummy = new ListNode(0), tail = dummy;
            
            // iterate two list, add each position until 2 lists are finished && left equals to 0
            while(!(l1 == null && l2 == null && left == 0)){
                // is number1 finished?
                int add1 = l1 != null ? l1.val : 0;
                // is number2 finished?
                int add2 = l2 != null ? l2.val : 0;
                int sum = add1 + add2 + left;
                left = sum / 10;
                ListNode newNode = new ListNode(sum % 10);
                tail.next = newNode;
                tail = newNode;
                
                if(l1 != null) l1 = l1.next;
                if(l2 != null) l2 = l2.next;
            }
            
            return dummy.next;
        }
    

    Just another version in java.


  • 35
    P

    By the way, I was offered a job at Google, and I work there as a SWE now. Guys, practice leet code oj online, it really really helps!


  • 1
    L
        public ListNode addTwoNumbers(ListNode l1, ListNode l2)
        {
            ListNode head = new ListNode(0); // l3 = l1 + l2;
            ListNode l3 = head;
            int sum = 0;
            /** If both are not done **/
            while (l1 != null && l2 != null)
            {
                sum /= 10;
                sum += l1.val + l2.val;
                l1 = l1.next;
                l2 = l2.next;
                l3.next = new ListNode(sum % 10);
                l3 = l3.next;
            }
            /** If one of them is not done **/
            if (l1 != null || l2 != null)
            {
                ListNode l = (l1 != null) ? l1 : l2;
                while (l != null)
                {
                    sum /= 10;
                    sum += l.val;
                    l3.next = new ListNode(sum % 10);
                    l3 = l3.next;
                    l = l.next;
                }
            }
            if (sum / 10 == 1) l3.next = new ListNode(1);
            return head.next;
        }
    

    How about my solution? It is similar to potpie's solution, but it takes the problem in 2 stages. The 1st stage is where both ListNodes are not finished. The second stage takes care of the case where one of them is done. I know that my code is less compact, but it reduces unnecessary if statement, i.e, if you have l1 very long and l2 very short, after l2 is finished, it doesn't check l2 anymore.


  • 0
    O

    congrats, and thank you so much for the solution.


  • 0

    very beautifuly


  • 1
    P

    I have a recursive version

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        return addTwoNumbers(l1, l2, 0);
    }
    
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2, int carry) {
        if(l1 == NULL)
            return addTwoNumbers(l2, carry);
        if(l2 == NULL)
            return addTwoNumbers(l1, carry);
        l1->val += (l2->val + carry);
        l1->next = addTwoNumbers(l1->next, l2->next, l1->val / 10);
        l1->val %= 10;
        return l1;
    }
    
    ListNode *addTwoNumbers(ListNode *l, int carry) {
        if(l == NULL)
            if (carry)
                return new ListNode(carry);
            else
                return NULL;
        l->val += carry;
        l->next = addTwoNumbers(l->next, l->val / 10);
        l->val %= 10;
        return l;
            
    }

  • 0
    T
    This post is deleted!

  • 0
    Z

    Recursive version. Early terminate when there is only one list. Should be easy to change to non-recursive one?

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }
    public ListNode add(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null) return carry != 0 ? new ListNode(carry) : null;
        carry += (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
        if (carry < 10 && (l1 == null || l2 == null)) {
            ListNode n = (l1!=null ? l1 : l2);
            n.val = carry;
            return n;
        }
        ListNode cur = new ListNode(carry%10);
        cur.next = add(l1 != null ? l1.next : null, l2!=null ? l2.next : null, carry/10);
        return cur;
    }

  • 10
    R

    I have done the same as you in C++:

    class Solution {
        
    public:
    
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
        {
            ListNode stackAnchor(0);
            ListNode* tail = &stackAnchor;
    
            div_t sum = { 0, 0 };
            while(sum.quot > 0 || l1 || l2)
            {
                if (l1)
                {
                    sum.quot += l1->val;
                    l1 = l1->next;
                }
                if (l2)
                {
                    sum.quot += l2->val;
                    l2 = l2->next;
                }
                sum = div(sum.quot, 10);
                
                tail->next = new ListNode(sum.rem);
                tail = tail->next;
            }
    
            return stackAnchor.next;
        }
        
    };
    

    The only differences in term of performances are:

    • I don't allocate an extra element because I can put it on the stack, is C++.
    • I perform division and module by 10 at one single step tanks to std::div that should be solved with one single assembly instruction, divisions are quite expensive.

  • 0
    J

    After playing around for some time I came up with the same idea (as I can see now, many guys came up with similar one), but I want to thank you for the tip about div, and I like your idea with first item.


  • 0
    D

    My solution is in Java.It doesn't need too many extra nodes, just use the old linked list.But it doesn't looks very compact, and takes 752 ms, maybe someone can give me an optimal version.

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int carry = 0;
            ListNode head, n1, n2;
            n1 = new ListNode(0);
            n2 = new ListNode(0);
            n1.next = l1;
            n2.next = l2;
            head = l1;
            while(l1 != null && l2!= null){
                n1 = l1;
                n2 = l2;
                carry += l1.val +l2.val;
                l1.val = carry % 10;
                carry /= 10;
                l1 = l1.next;
                l2 = l2.next;
            }
            
            //if l1 gets the end, let the linked list point to the l2
            if(l1 == null){
                l1 = l2;
                n1.next = l1;
            }
    
            while(l1 != null){
                n1 = l1;
                carry += l1.val;
                l1.val = carry % 10;
                carry /= 10;
                l1 = l1.next;
            }   
            if(carry == 1){
                n1.next = new ListNode(1);
            }
            
            return head;
        }
    }

  • 0
    M

    I have to say that yours is extraordinary!!


Log in to reply
 

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