/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null)return l2;
        if(l2 == null)return l1;
        //反转
        ListNode pre1 = null;
        ListNode cur1 = l1;
        while(cur1 != null){
            ListNode temp = cur1.next;
            cur1.next = pre1;
            pre1 = cur1;
            cur1 = temp;
        }

        ListNode pre2 = null;
        ListNode cur2 = l2;
        while(cur2 != null){
            ListNode temp = cur2.next;
            cur2.next = pre2;
            pre2 = cur2;
            cur2 = temp;
        }

        ListNode head = new ListNode(0);
        ListNode headBak = head;
        int res = 0;
        while(pre1 != null || pre2 != null){
            res = res + (pre1 != null ? pre1.val : 0) + (pre2 != null ? pre2.val : 0);
            head.next = new ListNode(res%10);
            pre1 = (pre1 != null ? pre1.next : null);
            pre2 = (pre2 != null ? pre2.next : null);
            head = head.next;
            res = res/10;
        }
        if(res != 0){
            head.next = new ListNode(res);
        }
        ListNode resHead = null;
        ListNode resHeadF = headBak.next;
        while(resHeadF != null){
            ListNode temp = resHeadF.next;
            resHeadF.next = resHead;
            resHead = resHeadF;
            resHeadF = temp;
        }
        return resHead;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int sum = 0;
        ListNode head = null;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            sum = sum + (stack1.isEmpty()?0:stack1.pop());
            sum = sum + (stack2.isEmpty()?0:stack2.pop());
            ListNode node = new ListNode(sum%10);
            node.next = head;
            head = node;
            sum = sum/10;
        }
        if(sum != 0){
            ListNode node = new ListNode(sum);
            node.next = head;
            head = node;
        }
        return head;
    }
}