[LeetCode] 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:

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

两数相加II。这题思路跟[LeetCode] 2. Add Two Numbers很相似。唯一的不同点在于，第2题是从最低位到最高位做加法，只要记得进位即可；但是445是在逆向做加法，linked list的头结点是数字的最高位，先reverse两个list然后再做加法的思路会略显麻烦。如下这个例子实际是在算7243 + 564 = 7807

Example:

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

这题的思路是先用两个stack分别存住两个list的nodes，然后pop出来的时候做加法。这样就不需要操心reverse linked list这件事了。但是这个题依然很麻烦，（照着这个例子讲）算出了个位数7之后，算十位数的时候，要把十位数的next指针再指向个位数，cur指针再从个位数移动到十位数。实际上cur指针是从右往左推进的（7 <- 8 <- 0 <- 7）。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 3         Stack<Integer> s1 = new Stack<>();
 4         Stack<Integer> s2 = new Stack<>();
 5         while (l1 != null) {
 6             s1.push(l1.val);
 7             l1 = l1.next;
 8         }
 9         while (l2 != null) {
10             s2.push(l2.val);
11             l2 = l2.next;
12         }
13         ListNode cur = new ListNode(0);
14         int sum = 0;
15         while (!s1.isEmpty() || !s2.isEmpty()) {
16             if (!s1.isEmpty()) {
17                 sum += s1.pop();
18             }
19             if (!s2.isEmpty()) {
20                 sum += s2.pop();
21             }
22             cur.val = sum % 10;
23             ListNode head = new ListNode(sum / 10);
24             head.next = cur;
25             cur = head;
26             sum /= 10;
27         }
28         if (cur.val == 0) {
29             return cur.next;
30         } else {
31             return cur;
32         }
33     }
34 }

JavaScript实现

 1 /**
 2  * @param {ListNode} l1
 3  * @param {ListNode} l2
 4  * @return {ListNode}
 5  */
 6 var addTwoNumbers = function(l1, l2) {
 7     let s1 = [];
 8     let s2 = [];
 9     while (l1 !== null) {
10         s1.push(l1.val);
11         l1 = l1.next;
12     }
13     while (l2 !== null) {
14         s2.push(l2.val);
15         l2 = l2.next;
16     }
17 
18     let cur = new ListNode(0);
19     let sum = 0;
20     while (s1.length || s2.length) {
21         if (s1.length) {
22             sum += s1.pop();
23         }
24         if (s2.length) {
25             sum += s2.pop();
26         }
27         cur.val = sum % 10;
28         let head = new ListNode(Math.floor(sum / 10));
29         head.next = cur;
30         cur = head;
31         sum = Math.floor(sum / 10);
32     }
33     if (cur.val === 0) {
34         return cur.next;
35     } else {
36         return cur;
37     }
38 };