题目描述
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.
与第2题类似，只不过这次的链表顺序跟2题链表顺序不一样。
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
解题思路
方案一（不可以）：
将链表转为数字，然后进行数字加减，再将数字转为链表。以example为例，就是写成7243+564=7807
再将7807 构建为链表：7 -> 8 -> 0 -> 7
问题：当给一个特别大的数（大于Integer.MAX_VALUE）就发生了越界。方案行不通。
方案二
链表问题还是按照链表的方法进行处理。由于低位在末尾，需要先加低位然后再高位。想到使用栈（先进后出）的特点。先将两个链表依次入栈，然后再同时出栈 相加。
关键点：对于进位的处理。使用一个变量sum，当和>=10时候，sum/=10是等于1的。当sum<10，sum/=10 是等于0 的，而下一位运算会在sum基础上继续。
题解
从题2中受到启发，循环条件是：
(!stack1.isEmpty() || !stack2.isEmpty() || sum != 0)
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
ListNode p = l1;
while(p != null){
stack1.push(p);
p =p .next;
}
p = l2;
while(p != null){
stack2.push(p);
p = p.next;
}
ListNode dummy = new ListNode(-1);
int sum = 0;
while(!stack1.isEmpty() || !stack2.isEmpty() || sum != 0){
if (!stack1.isEmpty()) sum+= stack1.pop().val;
if (!stack2.isEmpty()) sum+= stack2.pop().val;
ListNode node = new ListNode(sum % 10);
node.next = dummy.next;
dummy.next = node;
sum = sum / 10;
}
return dummy.next;
}
实际上每次将进位的1加到了第一个栈的栈顶元素上，如果没有则创建一个为1的结点。整体思路跟上面差不多，leetcode判题这个内存较小。。。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
ListNode p = l1;
while(p != null){
stack1.push(p);
p =p .next;
}
p = l2;
while(p != null){
stack2.push(p);
p = p.next;
}
ListNode dummy = new ListNode(-1);
int add = 0;
int sum = 0;
while(!stack1.isEmpty() || !stack2.isEmpty()){
if (!stack1.isEmpty()) sum+= stack1.pop().val;
if (!stack2.isEmpty()) sum+= stack2.pop().val;
if (sum >= 10){
if (!stack1.isEmpty()){
stack1.peek().val += sum /10;
}
else {
stack1.push(new ListNode(sum/10));
}
}
ListNode node = new ListNode(sum % 10);
node.next = dummy.next;
dummy.next = node;
sum = 0;
}
return dummy.next;
}
