Easy O(n) Java Solution using Stack

• ``````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);
sum /= 10;
}

return list.val == 0 ? list.next : list;
}
}
``````

• nice solution

• @Hx2 It cannot pass the case [1] + [9]

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

• This sum variable used is sooo cool.

• 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);
}
return res->val? res : res->next;
}
``````

• Stack is not recommended in 《Thinking in Java》. its efficiency is too slow.
We can use Hashmap to solve this problem with the similar idea.

• I do not understand the meaning in the code "list = head;" in the java version.

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

• This post is deleted!

• Frankly, it goes against the 'follow up' below.

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.

see problem 206 for more detail, and here goes the concise code for 206.

``````public class Solution {
}
}
}
``````

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

}
}

``````

• If you do the `sum /= 10` in the creation of the ListNode, you'll save a line :)

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

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