/*
You are given two non-empty linked lists representing
two non-negative integers. The digits are stored in
reverse order 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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807
*/
此题不能用暴力法，即将 List1 和 List2 都转化为数，然后相加，然而笔者实现了这一暴力算法过程：
- 利用 10 的乘方来恢复 List 所表示的数，再将两个数相加，将和作为字符串处理，将字符串中每一个字符所代表的数字插入到一个空链表头引领的 List 中，最后返回空链表头的下一个节点
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1Num = 0;
int num1 = 0;
int l2Num = 0;
int num2 = 0;
while(l1 != null) {
l1Num = l1Num + l1.val * (int)Math.pow(10, num1);
l1 = l1.next;
num1++;
}
while(l2 != null) {
l2Num = l2Num + l2.val * (int)Math.pow(10, num2);
l2 = l2.next;
num2++;
}
int sum = l1Num + l2Num;
// System.out.println(l1Num + " " + l2Num);
String sumString = sum + "";
System.out.println(sumString);
ListNode emptyHead = new ListNode(0);
ListNode curr = emptyHead;
for(int i = sumString.length() - 1; i >= 0; i--) {
ListNode Num = new ListNode(Integer.valueOf(sumString.charAt(i) + ""));
curr.next = Num;
curr = curr.next;
}
return emptyHead.next;
}
这样虽然能够满足题目中给出的例子：（结果是 807 对应的 7 -> 0 -> 8）
public static void main(String[] args) {
ListNode l11 = new ListNode(2);
ListNode l12 = new ListNode(4);
ListNode l13 = new ListNode(3);
l11.next = l12;
l12.next = l13;
ListNode l21 = new ListNode(5);
ListNode l22 = new ListNode(6);
ListNode l23 = new ListNode(4);
l21.next = l22;
l22.next = l23;
ListNode head = addTwoNumbers(l11,l21);
while(head != null) {
System.out.print(head.val);
head = head.next;
}
}
但是它存在一个致命的 Overflow 问题，即处理 long 类型整数时，会出现溢出：
public static void main(String[] args) {
ListNode l11 = new ListNode(9);
ListNode l21 = new ListNode(1);
ListNode l22 = new ListNode(9);
ListNode l23 = new ListNode(9);
ListNode l24 = new ListNode(9);
ListNode l25 = new ListNode(9);
ListNode l26 = new ListNode(9);
ListNode l27 = new ListNode(9);
ListNode l28 = new ListNode(9);
ListNode l29 = new ListNode(9);
ListNode l210 = new ListNode(9);
l21.next = l22;
l22.next = l23;
l23.next = l24;
l24.next = l25;
l25.next = l26;
l26.next = l27;
l27.next = l28;
l28.next = l29;
l29.next = l210;
ListNode head = addTwoNumbers(l11,l21);
while(head != null) {
System.out.print(head.val);
head = head.next;
}
}
- 其结果并不是 10000000000，而是 8045600141
故在提交时也不能通过
弃之，改用他法
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
// 与上法相同，创建空链表头，用来生成新链表返回空链表头下一个节点
ListNode emptyHead = new ListNode(0);
ListNode curr = emptyHead;
ListNode p = l1;
ListNode q = l2;
// carry 是进位符，如果两个节点中的数字相加导致向下一位进位，则将 carry 置成 1，不进位 carry 为 0，所以后续 carry 参与节点中数字的相加
int carry = 0;
while(p != null || q != null) {
int x;
int y;
if(p == null) {
x = 0;
}
else {
x = p.val;
}
if(q == null) {
y = 0;
}
else {
y = q.val;
}
// 得到总和为表一节点数字加表二节点数字加进位符
int sum = x + y + carry;
// 该节点的新数字为综合除以 10 之后的余数
int newCurrNumber = (sum) % 10;
ListNode newNumber = new ListNode(newCurrNumber);
// 连接上之前的链表
curr.next = newNumber;
curr = curr.next;
// 如果和大于等于 10，进位符为 1，下一位（节点）的两个数进行计算时要加进位符 1，否则不进位（进位符为 0）
if(sum >= 10) {
carry = 1;
}
else {
carry = 0;
}
// l1 和 l2 向后遍历
if(p != null) {
p = p.next;
}
if(q != null) {
q = q.next;
}
}
// 如果最后一次运算过后，进位符仍然为 1，则说明产生了新的位，为表示新数字的链表创建一个新的节点
if(carry == 1) {
curr.next = new ListNode(carry);
}
// 返回空链表头的下一个节点
return emptyHead.next;
}
这样就通过了测试
