给两数相加二
1.题目
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]示例2：
代码语言：javascript复制输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]示例3：
代码语言：javascript复制输入：l1 = [0], l2 = [0]
输出：[0]提示：
- 链表的长度范围为
[1, 100] 0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。
2.题解
先自定义ListNode
代码语言：javascript复制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; }
}
1.我的题解
代码语言：javascript复制/**
* 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 input1, ListNode input2) {
ListNode ln1 = turnListNode(input1);
print(ln1);
ListNode ln2 = turnListNode(input2);
print(ln2);
if(ln1 == null && ln2 == null){
return null;
}else if(ln1 == null){
return ln2;
}else if(ln2 == null){
return ln1;
}
ListNode result = new ListNode();
ListNode before = result;
int moreThanTen = 0;
int sum = 0;
while(ln1 !=null || ln2 != null){
sum = 0;
if(ln1!= null){
sum = ln1.val;
}
if(ln2!= null){
sum = ln2.val;
}
//进位
sum =moreThanTen;
if(sum>=10){
moreThanTen = 1;
}else{
moreThanTen = 0;
}
ListNode node = new ListNode(sum);
before.next = node;
before = node;
if(ln1!=null ) ln1 = ln1.next;
if(ln2!=null ) ln2 = ln2.next;
};
if(moreThanTen==1){
ListNode node = new ListNode(1);
before.next = node;
before = node;
}
result = result.next;
result = turnListNode(result);
return result;
}
private ListNode turnListNode(ListNode ln1) {
ListNode result = new ListNode();
ListNode before = result;
Stack<Integer> st = new Stack<Integer>();
while(ln1 != null){
st.push(ln1.val);
ln1 = ln1.next;
}
//st.push(ln1.val);
while(! st.empty()){
ListNode node = new ListNode(st.pop());
before.next = node;
before = before.next;
}
return result.next;
}
private void print(ListNode node) {
System.out.println("nprint ListNode:");
do{
System.out.print(node.val ",");
if(node.next!= null) node=node.next;
}while(node.next!= null);
System.out.print(node.val ",");
}
}2.官方题解（栈）
代码语言：javascript复制class Solution{
public ListNode addTwoNumbers(ListNode l1,ListNode l2){
Deque<Integer> stack1 = new ArrayDeque<Integer>();
Deque<Integer> stack2 = new ArrayDeque<Integer>();
while(l1 != null){
stack1.push(l1.val);
l1 = l1.next;
}
while(l2 != null){
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode ans = null;
while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
int a = stack1.isEmpty() ? 0 : stack1.pop();
int b = stack2.isEmpty() ? 0 : stack2.pop();
int cur = a b carry;
carry = cur /10;
cur %= 10;
ListNode curnode = new ListNode(cur);
curnode.next = ans;
ans = curnode;
}
return ans;
}
}
