Easy O(n) Java Solution using Stack


  • 89
    H
    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;
        }
    }
    

  • 0
    B

    nice solution


  • 0
    L

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


  • 4
    O

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

  • 3
    H

    This sum variable used is sooo cool.


  • 3
    S

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

  • -5
    N

    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.


  • 0
    S

    I do not understand the meaning in the code "list = head;" in the java version.
    Please explain in more detail.


  • 0
    A

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


  • 0
    S
    This post is deleted!

  • 2
    A

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


  • 0
    A

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


  • 0
    S

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


  • 0
    A

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

  • 0
    S

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


  • 0
    A

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

  • 0
    O

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

  • 0
    S

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


  • 0
    S

    @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


  • 0
    S

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


Log in to reply
 

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