题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
2. 两数相加（中等） - 图1
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]


提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解题思路

1、模拟计算（不可行）

分别遍历两个链表，计算两个操作数是多少，求和后再逐位生成新的链表。

模拟计算的方式首先于数据类型的限制，无法用于大数加法。这个思路事实上是一个死胡同，无法解决问题。

2、逐位计算

因为两个链表存储的每位数字都是按照 逆序 的方式存储，所以可以利用大数加法的思想，只维护一个进位变量，逐位计算。

答案

1、模拟计算（不可行）

虽然这个答案是错误的，但也记录一下。

  1. class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.         // 两个操作数
  4.         int a = 0, b = 0;
  6.         // 求 a
  7.         int multiples = 1;
  8.         while (true) {
  9.             if (l1.next != null) {
  10.                 a += l1.val * multiples;
  12.                 multiples *= 10;
  13.                 l1 = l1.next;
  15.                 continue;
  16.             }
  18.             a += l1.val * multiples;
  19.             multiples = 1;
  20.             break;
  21.         }
  23.         // 求 b
  24.         while (true) {
  25.             if (l2.next != null) {
  26.                 b += l2.val * multiples;
  28.                 multiples *= 10;
  29.                 l2 = l2.next;
  31.                 continue;
  32.             }
  34.             b += l2.val * multiples;
  35.             break;
  36.         }
  38.         // 求 a + b 的和
  39.         int sum = a + b;
  40. //        System.out.println(a);
  41. //        System.out.println(b);
  42. //        System.out.println(sum);
  44.         // 生成链表
  45.         ListNode result = new ListNode();
  46.         ListNode current = result;
  48.         int temp = 0;
  49.         while (true) {
  50.             if (sum >= 10) {
  51.                 temp = sum % 10;
  52.                 sum /= 10;
  54.                 current.val = (int) temp;
  56.                 ListNode newNode = new ListNode();
  57.                 current.next = newNode;
  58.                 current = newNode;
  60.                 continue;
  61.             } else {
  62.                 temp = sum;
  64.                 current.val = (int) temp;
  65.                 break;
  66.             }
  67.         }
  69. //        System.out.println(result);
  71.         return result;
  72.     }
  73. }

2、逐位计算

  1. class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.         ListNode root = new ListNode(-1);
  4.         ListNode cursor = root;
  6.         // 进位t
  7.         int t = 0;
  8.         while (l1 != null || l2 != null || t != 0) {
  9.             if (l1 != null) {
  10.                 t += l1.val;
  11.                 l1 = l1.next;
  12.             }
  14.             if (l2 != null) {
  15.                 t += l2.val;
  16.                 l2 = l2.next;
  17.             }
  19.             cursor.next = new ListNode(t % 10);
  20.             cursor = cursor.next;
  21.             t /= 10;
  22.         }
  24.         return root.next;
  25.     }
  26. }