445、两数相加II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
题解
1、利用栈的先进后出特点
/**
* 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<>();
// 处理特殊case
if (l1 == null){
return l2;
}
if (l2 == null){
return l1;
}
// 将链表的数据push到栈中
ListNode p = l1;
while(p != null){
s1.push(p.val);
p = p.next;
}
p = l2;
while(p != null){
s2.push(p.val);
p = p.next;
}
// 模拟计算
int acc = 0,t = 0;
Stack<Integer> res = new Stack<>();
while (!s1.isEmpty() && !s2.isEmpty()){
t = s1.peek() + s2.peek() + acc;
s1.pop();
s2.pop();
acc = t/10;
t = t % 10;
res.push(t);
}
while(!s1.isEmpty()){
t = s1.peek() + acc;
s1.pop();
acc = t/10;
t = t % 10;
res.push(t);
}
while(!s2.isEmpty()){
t = s2.peek() + acc;
s2.pop();
acc = t/10;
t = t % 10;
res.push(t);
}
if (acc != 0) {
res.push(acc);
}
// 处理结果：将栈数据变成链表
ListNode ans = new ListNode(-1);
p = ans;
while(!res.isEmpty()) {
p.next = new ListNode(res.peek());
res.pop();
p = p.next;
}
return ans.next;
}
}
// 优化处理，一个人循环模拟加法运算，头插法创建链表
/**
* 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<>();
// 处理特殊case
if (l1 == null){
return l2;
}
if (l2 == null){
return l1;
}
// 将链表的数据push到栈中
ListNode p = l1;
while(p != null){
s1.push(p.val);
p = p.next;
}
p = l2;
while(p != null){
s2.push(p.val);
p = p.next;
}
// 模拟计算
int acc = 0,a,b,t;
ListNode res = new ListNode(-1);
// 一个循环模拟运算，而且可以处理最高位进位
while (!s1.isEmpty() || !s2.isEmpty() || acc != 0) {
a = s1.isEmpty() ? 0:s1.peek();
b = s2.isEmpty() ? 0:s2.peek();
if (!s1.isEmpty()) {s1.pop();}
if (!s2.isEmpty()) {s2.pop();}
t = a + b + acc;
acc = t / 10;
t = t % 10;
// 头插法创建链表
ListNode node = new ListNode(t);
node.next = res.next;
res.next = node;
}
return res.next;
}
}
2、将链表翻转处理
/**
* 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) {
ListNode header = new ListNode(0);
ListNode tmp = header;
l1 = reverse(l1);
l2 = reverse(l2);
int carry = 0;
int sum = 0;
while(l1!=null||l2!=null){
if(l1!=null&&l2!=null){
sum = l1.val+l2.val + carry;
l1 = l1.next;
l2 = l2.next;
}else if(l1!=null){
sum = l1.val+carry;
l1= l1.next;
}else{
sum = l2.val+carry;
l2 = l2.next;
}
carry = sum>=10?1:0;
sum = sum%10;
header.next = new ListNode(sum);
header = header.next;
if((l1==null || l2==null)&& carry==0){
header.next = l1!=null?l1:l2;
return reverse(tmp.next);
}
}
if(carry!=0){
header.next = new ListNode(carry);
header.next.next = null;
}
return reverse(tmp.next);
}
// 链表翻转函数
public ListNode reverse(ListNode node){
ListNode pre = null;
ListNode next = null;
while(node!=null){
next = node.next;
node.next = pre;
pre = node;
node = next;
}
return pre;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
