Add Two Numbers


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++; }

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;

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; } };

The carry logic exploded my head, so I decided to just convert both lists to integers, add them with the builtin 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, length1); } 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 ultracritical.

@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?

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

@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.

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; } };

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

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; }

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); }

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)