# 445 Add Two Numbers II

把兩個整數相加，整數存在LinkedList裡，每個位數放在LinkedNode中。

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Concept:

the first idea came into my mind is reverse l1 and l2, than add each digit by order. however, the followup said don't modify l1 and l2.our goal is to add from the last node to first node.we can do that by stack.

Pseudocode:

    go through l1 and l2, and keep all nodes in stack1 and stack2

    create a new linked list to save result

    pt=result

    while stack1 || stack2 is not empty

        s1=0, s2=0

        if(stack1 is not empty)

            s1 = stack1.pop.val

        if(stack2 is not empty)

            s2 = stack2.pop.val

        pt.next = new ListNode(s1+s2)



    reverse result

完整程式碼:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {


        ListNode pt1 = l1;
        Deque<ListNode> stack1 = new ArrayDeque<>();
        while(pt1!=null){
            stack1.push(pt1);
            pt1 = pt1.next;
        }
        ListNode pt2 = l2;
        Deque<ListNode> stack2 = new ArrayDeque<>();
        while(pt2!=null){
            stack2.push(pt2);
            pt2 = pt2.next;
        }

        ListNode result = new ListNode(0);
        ListNode pt = result;
        int i =0;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            int s1=0, s2=0;
            if(!stack1.isEmpty()){
                s1=stack1.pop().val;
            }
            if(!stack2.isEmpty()){
                s2=stack2.pop().val;
            }
            pt.next = new ListNode((s1+s2+i)%10);
            i = (s1+s2+i)/10;
            pt = pt.next;
        }
        if(i>0){
            pt.next = new ListNode(i);
        }

        //reverse result
        pt = result.next;
        result = null;
        while(pt!=null){
            ListNode tmp = pt.next;
            pt.next = result;
            result = pt;
            pt = tmp;

        }
        return result;
    }
}