Add Two Numbers


  • 0

    Click here to see the full article post


  • 0
    L

    dummyHead is a good way


  • 0

    Suggestion:
    In terms of "carry = sum / 10", from the code it looks like for every operation of two nodes' values' sum, it has to do a division calculation to get "carry". However, in some cases this division operation may not be necessary to be conducted, such as when sum is less than 10. In addition, due to this problem's feature, two nodes' values' sum will be exceed 20, which means we could simply assign the value of "1" to "carry", or add "1" to "carry" if "sum > 10" instead of doing a division operation.

    Could it be improved in the following two ways due the fact that division has a higher computational cost than comparison and plus (correct me if I am wrong) instead of "carry = sum / 10;"?:

    if (sum >= 10) {
        carry++;
    }
    

  • 0

    Correction from last post:
    "In addition, due to this problem's feature, two nodes' values' sum will NOT exceed 20, ..."
    "Could it be improved in the following way..."


  • 0

    Tried my suggestion but it might add "1" into the rear of the result list, hmm let me check what went wrong.


  • 0
    H

    We can save the extra space by overwriting the l1 or l2 rite. so that space complexity can be reduced O(n) to O(1);

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            head=l1;
            carry=0;
            l1.val=l1.val+l2.val;
            if l1.val>9:
                l1.val=l1.val%10;
                carry=1;
                
            while l1.next!=None and l2.next!=None:
                l1=l1.next;
                l2=l2.next;
                l1.val=l1.val+l2.val+carry;
                if l1.val>9:
                    l1.val=l1.val%10;
                    carry=1;
                else:
                    carry=0;
            
            if l2.next!=None:
                l1.next=l2.next;
                
            while l1.next!=None:
                l1=l1.next;
                l1.val=l1.val+carry;
                if l1.val>9:
                    l1.val=l1.val%10;
                    carry=1;
                else:
                    carry=0;
                    
            if carry==1:
                last=ListNode(1);
                l1.next=last;
            
            return head;
    

  • 0
    E

    i think dummyhead is a perfect idea , this thinking is important , maybe your method is more effeciency


  • 0
    S

    So who can tell me the algorithm that has the most efficient time complexity ,it took 40ms to run my algorithm.......


  • 0
    X

    make it more concise

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

  • 0
    S

    The carry logic exploded my head, so I decided to just convert both lists to integers, add them with the built-in addition operator, and then turn the result back into a list.

    var addTwoNumbers = function(l1, l2) {
        /** Recursive function to convert a linked list to an integer
         *  @param {ListNode} lh
         *  @param {int} power
         *  @return {int}
         */
        function linkListToInt(lh, power) {
            if(lh.next === null) {
                return lh.val * Math.pow(10, power);
            } else {
                return lh.val * Math.pow(10, power) + linkListToInt(lh.next, power+1);
            }
        }
    
        /** Recursive function to convert an integer to a linked list
         *  @param {int} input
         *  @return {ListNode}
         */
        function intToLinkList(input, length) {
            // Return null if there's nothing left to add, truncating the list if we're at the end
            // of the number
            
            // Otherwise, create a node and try to create the next one
            var leastSignificant = input % 10;
            var firstNode = new ListNode(leastSignificant);
            // Cast this value to integer with a bitwise OR just to be sure
            var rightShifted = (input - leastSignificant)/10 | 0;
            if(length === 1) {
                firstNode.next = null;
            } else {
                firstNode.next = intToLinkList(rightShifted, length-1);
            }
            return firstNode;
        }
    
        var firstInt = linkListToInt(l1, 0);
        var secondInt = linkListToInt(l2, 0);
        var sum = firstInt + secondInt;
        var length = sum.toString().length;
        console.log('sum is: '+sum+'\nlength is: '+length)
        var output = intToLinkList(sum, length);
        return output;
    }
    

    I realize I lose points here for using int.toString().length, but as far as I'm concerned, that's the most intuitive way to do it, therefore it requires the least thinking, and therefore it's a decent choice when performance is not ultra-critical.


  • 0

    @ssonicblue said in Add Two Numbers:

    The carry logic exploded my head

    Hmm, didn't you learn that in elementary school like every other little child? :-)

    And forget efficiency. Your solution is wrong already for [1,1,1,1,1,1,1,1,1,1,1] + [1,1,1,1,1,1,1,1,1,1,1]. Claims the answer is [2,-4,-7,0,-5,-4,-7,-2,-7,0,-2].

    @1337c0d3r I'm very surprised that the OJ only tests very small integers. What's up with that?


  • 0

    @StefanPochmann Just added the test case you mentioned and also one other test case which contains very large integer.


  • 0
    I

    @ssonicblue I had the same idea, but my version got shot down by the OJ when it tested a number that was larger than an integer's maximum value (Though I just saw that the test case was added just last week, haha)

    Ended up coming up with something very similar to the editorial answer logic wise, though my execution was sloppier.


  • 0
    H

    Ended up with a recursive solution.

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

  • 0
    P

    So what I want to say is why the reault is [0,10] when l1 is [9,9] and l2 is [1].I think the right answer maybe [0,0,1],Why?


  • 0
    A
    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            result = []
            curr = None
            carry = 0
            while l1 is not None and l2 is not None:
                carry, result = self._addnumbers(l1.val, l2.val, carry, result)
                l1 = l1.next
                l2 = l2.next
            
            while l1 is not None:
                carry, result = self._addnumbers(l1.val, 0, carry, result)
                l1 = l1.next
            
            while l2 is not None:
                carry, result = self._addnumbers(0, l2.val, carry, result)
                l2 = l2.next
    
            if carry != 0:
                result.append(carry)
            
            return result
            
        def _addnumbers(self, val1, val2, carry, result):
            curr = ListNode((val1 + val2 + carry) % 10 )
            carry = (val1 + val2 + carry) / 10
            result.append(curr.val)
            return carry, result
    

  • 0
    I

    Quite happy that my solution outperformed 96% of Java submission. Share with you guys. :)

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode result, node;
    	int temp, carry = 0;
    
    	if (l1 == null && l2 == null) {
    		return null;
    	}
    	
    	result = new ListNode(0);
    	node = result;
    
    	do  {
    		temp = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
    		carry = temp < 10 ? 0 : 1;
    
    		node.next = new ListNode(temp % 10);
    		node = node.next;
    
    		if (l1 != null)
    			l1 = l1.next;
    
    		if (l2 != null)
    			l2 = l2.next;
    	} while (l1 != null || l2 != null || carry > 0);
    
    	return result.next;
    }

  • 0
    I

    Lol, it turned out that the performance varies a lot with different submissions. The previous post will normally land at around 30%, which isn't actually a very efficient solution...


  • 0
    L
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
    
        addRecursively(result, l1, l2);
    
        return result;
    }
    
    ListNode addRecursively(ListNode result, ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return result;
    
        if (l1 == null) l1 = new ListNode(0);
        if (l2 == null) l2 = new ListNode(0);
    
        int sum = result.val + l1.val + l2.val;
        result.val = sum % 10;
    
        int passingDigit = sum / 10;
    
        if (l1.next == null && l2.next == null && passingDigit == 0)  {
            return result;
        } else {
            result.next = new ListNode(passingDigit);
        }
    
        return addRecursively(result.next, l1.next, l2.next);
    }

  • -1
    L

    I am a new learner for python, my code got the final solution, but there is a error in my code. who can give me some advices. thanks!!!

    list1 = [2,4,3]
    list2 = [5,6,4]
    resultList=[0,0,0]
    number = 0
    def addFunctionForTwoList(list1,list2,number):
        count=[0,0,0]
        if (list1[number]+list2[number])>=10:
            count[number] = count[number]+list1[number]+list2[number]-10
            count[number+1] = 1
            return count
        else:
            count[number] = count[number]+list1[number]+list2[number]
            return count
    
    resultList1=addFunctionForTwoList(list1,list2,0)
    resultList2=addFunctionForTwoList(list1,list2,1)
    resultList3=addFunctionForTwoList(list1,list2,2)
    resultList[0]=resultList1[0]+resultList2[0]+resultList3[0]
    resultList[1]=resultList1[1]+resultList2[1]+resultList3[1]
    resultList[2]=resultList1[2]+resultList2[2]+resultList3[2]
    print(resultList)
    

Log in to reply
 

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