public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
while(l1 != null) {
s1.push(l1.val);
l1 = l1.next;
};
while(l2 != null) {
s2.push(l2.val);
l2 = l2.next;
}
int sum = 0;
ListNode list = new ListNode(0);
while (!s1.empty()  !s2.empty()) {
if (!s1.empty()) sum += s1.pop();
if (!s2.empty()) sum += s2.pop();
list.val = sum % 10;
ListNode head = new ListNode(sum / 10);
head.next = list;
list = head;
sum /= 10;
}
return list.val == 0 ? list.next : list;
}
}
Easy O(n) Java Solution using Stack



My solution uses one stack.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int n1 = 0, n2 = 0; for (ListNode i = l1; i != null; i = i.next) n1++; for (ListNode i = l2; i != null; i = i.next) n2++; Stack<Integer> st = new Stack(); int totn = Math.max(n1, n2); for (ListNode i = l1, j = l2; totn > 0; totn) { int a = 0, b = 0; if (totn <= n1) { a = i.val; i = i.next; } if (totn <= n2) { b = j.val; j = j.next; } st.push(a + b); } int c = 0; ListNode ans = null; while (!st.empty()) { ListNode i = new ListNode(st.pop()); int c1 = (c + i.val) / 10; i.val = (c + i.val) % 10; i.next = ans; ans = i; c = c1; } if (c > 0) { ListNode i = new ListNode(c); i.next = ans; ans = i; } return ans; }

AC solution with same idea for c++ version
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int> f1, f2; ListNode *res = new ListNode(0); int sum = 0; while(l1){f1.push(l1>val);l1 = l1>next;} while(l2){f2.push(l2>val);l2 = l2>next;} while(!f1.empty()  !f2.empty()){ if(!f1.empty()){sum+=f1.top();f1.pop();} if(!f2.empty()){sum+=f2.top();f2.pop();} res>val = sum % 10; ListNode* head = new ListNode(sum /= 10); head>next = res; res = head; } return res>val? res : res>next; }

@NiceAluo Could u pls explain it with a link or sth?
i just can't think it through why stack is not efficiency as HashMap.
i don't have this book, and i never read it..

Frankly, it goes against the 'follow up' below.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.In fact, the LIFO stack substantially reversed the lists.
But i can't figure out a better solution without reverse the list.
Maybe we can use the stack to preserve uncertain digits to save more space? such as [9 + 0], [8 + 1]...

@simonzheng1234 dude, i'm afraid i was not replying to u..
BTW, it feels kind of strange that two Chinese are communicating in English.

@AndyManastorm yes I see. I misunderstand as I am a new comer. Sorry for the inconvenience.

@simonzheng1234 now it's replying to u, bro. HAHA
list is a pointer to point at the head of this list.
each time, u may have to update the head(A), and create another new head(B) whose next is this head(A), and B becomes the new head. Recursion till both stack is Empty.
in the end, delete zero head.
you can create a fakeHead instead, and inject a new node between fakeHead and fakeHead.next each recursion, and return fakeHead.next finally.
see problem 206 for more detail, and here goes the concise code for 206.
public class Solution { public ListNode reverseList(ListNode head) { ListNode fakeHead = new ListNode(1); while(head != null){ ListNode tmp = head.next; head.next = fakeHead.next; fakeHead.next = head; head = tmp; } return fakeHead.next; } }

@AndyManastorm I understand the idea and I know you are right, it is a good idea to refer to problem 206 first as I do not think I know how to reverse a linked list. Thanks for your suggestion and I am gong over it now.

@Hx2 can you explain me this part of the code :
list.val = sum % 10;
ListNode head = new ListNode(sum / 10);
head.next = list;
list = head;
sum /= 10;
}return list.val == 0 ? list.next : list;

Simple fast solution by reversing linkedList
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode ll1 = reverse(l1); ListNode ll2 = reverse(l2); ListNode ans = new ListNode(0); ListNode curr = ans; int carry = 0; int sum = 0; while(ll1 != null  ll2 != null){ if(ll1 != null){ sum += ll1.val; ll1 = ll1.next; } if(ll2 != null){ sum += ll2.val; ll2 = ll2.next; } if(sum >= 10 ){ sum = sum%10; carry = 1; }else carry = 0; curr.next = new ListNode(sum); if(carry == 1) sum = 1; else sum = 0; curr = curr.next; } if(carry == 1){ curr.next = new ListNode(1); } return reverse(ans.next); } public ListNode reverse(ListNode head){ if(head == null  head.next == null){ return head; } ListNode newHead = reverse(head.next); head.next.next = head; head.next = null; return newHead; }

@Hx2 It doesn't handle the case when we have two linked lists with one no each [9] , [5] you should check outside the last while loop: if sum>0, then add a node for it

@ofLucas how can you add most significant digits first? Your solution adds 5+4 for a list like 5>8>>3>2, 4>2