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;
}
}
Is this Algorithm optimal or what?


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

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

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.

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.

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

Recursive version. Early terminate when there is only one list. Should be easy to change to nonrecursive 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; }

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.

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