两数相加

题面

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

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

你可以假设除了数字 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
• 题目数据保证列表表示的数字不含前导零

分析

• 显然，需要保存进位，并加到下一个节点中

• 对于这种操作两个链表的题目，都可以使用哑节点，来简化逻辑

• 当两个链表有一个没有遍历完或者进位仍大于 0，就不会停止循环

• 代码实现

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode() : val(0), next(nullptr) {}
   *     ListNode(int x) : val(x), next(nullptr) {}
   *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   * };
   */
  class Solution {
  public:
      ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
          ListNode* dummy = new ListNode(0);
          ListNode* cur = dummy;
          int carry = 0;
  
          while (l1 != nullptr || l2 != nullptr || carry > 0) {
              int val1 = (l1 != nullptr) ? l1->val : 0;
              int val2 = (l2 != nullptr) ? l2->val : 0;
  
              int sum = val1 + val2 + carry;
              carry = sum / 10;
              int curVal = sum % 10;
  
              cur->next = new ListNode(curVal);
              cur = cur->next;
  
              if (l1 != nullptr) l1 = l1->next;
              if (l2 != nullptr) l2 = l2->next;
          }
  
          ListNode* result = dummy->next;
          delete dummy;
          return result;
      }
  };

• 递归写法

  class Solution {
  public:
      // l1 和 l2 为当前遍历的节点，carry 为进位
      ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
          if (l1 == nullptr && l2 == nullptr && carry == 0) { // 递归边界
              return nullptr;
          }
  
          int s = carry;
          if (l1) {
              s += l1->val; // 累加进位与节点值
              l1 = l1->next;
          }
          if (l2) {
              s += l2->val;
              l2 = l2->next;
          }
  
          // s 除以 10 的余数为当前节点值，商为进位
          return new ListNode(s % 10, addTwoNumbers(l1, l2, s / 10));
      }
  };

• 也可以完全采用原地修改，为了避免一长一短，当 l2 长度大于 l1 时，就把两个链表交换，从而简化逻辑

  class Solution {
  public:
      // l1 和 l2 为当前遍历的节点，carry 为进位
      ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry = 0) {
          if (l1 == nullptr && l2 == nullptr) { // 递归边界
              return carry ? new ListNode(carry) : nullptr; // 如果进位了，就额外创建一个节点
          }
          if (l1 == nullptr) { // 如果 l1 是空的，那么此时 l2 一定不是空节点
              swap(l1, l2); // 交换 l1 与 l2，保证 l1 非空，从而简化代码
          }
          int sum = carry + l1->val + (l2 ? l2->val : 0); // 节点值和进位加在一起
          l1->val = sum % 10; // 每个节点保存一个数位（直接修改原链表）
          l1->next = addTwoNumbers(l1->next, (l2 ? l2->next : nullptr), sum / 10); // 进位
          return l1;
      }
  };