给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
思路:
- 毫无疑问,难点在于进位的处理,不需要进位的情况下,仅仅只是简单的同位相加
- 由于链表无法逆向遍历,需要通过其他手段辅助定位,如:链表反转,集合. 也可以通过转为10进制进行操作,不过这也是效率较低的选择(注意溢出)
- 在不知晓链表长度情况下,重建链表的效果要高于在原立案表上进行改动
代码1:
public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return l1;
ListNode temp = l1, cur;
long num1 = 0, num2 = 0;
//转为十进制数
while (temp != null) {
num1 = num1 * 10 + temp.val;
temp = temp.next;
}
temp = l2;
while (temp != null) {
num2 = num2 * 10 + temp.val;
temp = temp.next;
}
//求和并重构链表
num1 = num1 + num2;
if (num1 > 0) {
ListNode res = new ListNode(0);
res.next = temp;
int k;
while (num1 != 0) {
k = (int) (num1 % 10);
cur = res.next;
temp = new ListNode(k);
res.next = temp;
temp.next = cur;
num1 = num1 / 10;
}
} else {
temp = new ListNode(0);
}
return temp;
}
分析:
- 将链表转为十进制,自动进位进位处理,思路非常简单
- 测试用例中有许多越界数组,该方法还需要添加溢出的处理,例如按位数用数组分批存储数字等
代码2
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> sta1 = new Stack<Integer>();
Stack<Integer> sta2 = new Stack<Integer>();
Stack<Integer> sta = new Stack<Integer>();
//构建栈
while (l1 != null) {
sta1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
sta2.push(l2.val);
l2 = l2.next;
}
int c = 0;
//相加进位,压入新栈
while (!sta1.isEmpty() && !sta2.isEmpty()) {
int sum = sta1.pop() + sta2.pop() + c;
c = sum / 10;
sum = sum % 10;
sta.push(sum);
}
if (!sta2.isEmpty())
sta1 = sta2;
//为了应对两链表长度不同,另开一个循环进行处理
while (!sta1.isEmpty()) {
int sum = sta1.pop() + c;
c = sum / 10;
sum = sum % 10;
sta.push(sum);
}
if (c == 1)
sta.push(1);
ListNode dump = new ListNode(0);
ListNode ret = dump;
while (!sta.isEmpty()) {
dump.next = new ListNode((int) sta.pop());
dump = dump.next;
}
return ret.next;
}
分析:
- 使用栈进行操作,通过出栈操作达到逆向遍历链表的目的
- 此处也可以使用list等其他存储集合,但是效率都很低
代码3:
public ListNode addTwoNumbersBest(ListNode l1, ListNode l2) {
ListNode root1 = exec(l1);
ListNode root2 = exec(l2);
ListNode root = null, current = null;
int bits = 0;
ListNode n1 = root1, n2 = root2;
for(;n1 != null && n2 != null;n1 = n1.next, n2 = n2.next) {
int value = n1.val + n2.val + bits;
bits = value / 10;
if(root == null) {
root = new ListNode(value % 10);
current = root;
}else {
current.next = new ListNode(value % 10);
current = current.next;
}
}
for(;n1 != null;n1 = n1.next) {
int value = n1.val + bits;
bits = value / 10;
current.next = new ListNode(value % 10);
current = current.next;
}
for(;n2 != null;n2 = n2.next) {
int value = n2.val + bits;
bits = value / 10;
current.next = new ListNode(value % 10);
current = current.next;
}
if(bits != 0) {
current.next = new ListNode(bits);
current = current.next;
}
return exec(root);
}
//反转方法
public ListNode exec(ListNode root) {
ListNode node = root, previous = null;
while(node != null) {
ListNode next = node.next;
node.next = previous;
previous = node;
node = next;
}
return previous;
}
分析:
- 执行效率分布中非常靠前的方法
- 先反转链表,使其可以逆向遍历,之后使用相同的处理方式,计算和值
总结:
- 本题主要考察当顺序遍历无法满足结题要求时,对数据的处理方法
- 逆向链表与栈都是非常好的方法,若使用转为十进制进行操作,需要处理数值溢出问题
