2. 两数相加

难度: 中等

来源: 每日一题 2023.07.02

---

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 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
题目数据保证列表表示的数字不含前导零

/**
 * 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 l1, ListNode l2) {
    }
}

分析与题解

---

• 直接求解法

  对于两数相加这个问题来说,其实比较简单. 我们只需要根据下面的几种情况来处理.

  • 当前 l1 节点 和 l2 节点是否全部存在? 如果任意一个链表已经遍历完成, 那么我们就不用考虑这个链表,直接把另外一个链表添加到尾部即可.

  • 除了考虑 l1 节点 和 l2 节点是否全部存在外,还要考虑进位的问题,也就是 l1 节点 和 l2 节点 的值是否大于 10, 如果大于10 就要考虑进位情况,进位如果存在的话,依然会进入循环.

  • 上面两种情况都不满足的话,跳出循环. 把剩余的链表添加到尾部即可.

  只需要考虑上面三种情况即可完成整个题目的题解.

  题解代码如下所示.

  /**
  * 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 l1, ListNode l2) {
          ListNode headerNode = null;
          ListNode resultNode = null;
          int carryNumber = 0;
          // 判断条件1: l1 和 l2 是否全部存在
          // 判断条件2: 进位是否为0
          while ((l1 != null && l2 != null) || carryNumber != 0) {
              int resultNumber = 0;
              if (l1 != null) {
                  resultNumber += l1.val;
                  l1 = l1.next;
              }
              if (l2 != null) {
                  resultNumber += l2.val;
                  l2 = l2.next;
              }
              if (carryNumber != 0) {
                  resultNumber += carryNumber;
                  carryNumber = 0;
              }
              if (resultNumber >= 10) {
                  carryNumber = resultNumber/10;
                  resultNumber = resultNumber % 10;
              }
              if (headerNode == null) {
                  headerNode = new ListNode(resultNumber);
                  resultNode = headerNode;
              } else {
                  ListNode nextNode = new ListNode(resultNumber);
                  resultNode.next = nextNode;
                  resultNode = resultNode.next;
              }
          }
          // 添加了l1和l2的剩余链表到尾部即可
          if (l1 != null) {
              resultNode.next = l1;
          }
          if (l2 != null) {
              resultNode.next = l2;
          }
  
          return headerNode;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(min(m ,n)), 其中 n 和 m 为 l1 和 l2 的长度。
  • 空间复杂度: O(n), 需要 n - 1 个 nextNode临时变量

  结果如下所示.