445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        while(l1!=null){
            s1.add(l1.val);
            l1 = l1.next;
        }
        while(l2!=null){
            s2.add(l2.val);
            l2 = l2.next;
        }
        ListNode head = new ListNode(0);
        int temp = 0;
        while(! s1.empty() || !s2.empty()){
            if (! s1.empty()){
                temp += s1.pop();
            }
            if (! s2.empty()){
                temp += s2.pop();
            }
            head.val = temp%10;
            ListNode tempnode = new ListNode(temp/10);//考虑最后一步
            tempnode.next = head;//指向反转
            head = tempnode;//指向反转
            temp = temp/10;
        }
        return head.val == 0 ? head.next:head;//同样为了考虑最后一步
    }
}

链表加法的升级版,顺序反过来了: - 思路一致 - 不准反转 - 使用堆栈 - 由于链路指向反过来了,细节上需要注意