2. 两数相加

（1）题目

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

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

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

示例 1：

题目示例

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

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

示例 3：

1
2
输入：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
  • 题目数据保证列表表示的数字不含前导零

（2）题解

  • 循环对位相加

    对应位依次相加，利用额外变量追踪进位情况。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    int sum = 0; //记录当前位的和
    int carry = 0; //记录下一位的进位情况

    ListNode* result =new ListNode(-1);
    ListNode* cur = result; //result 固定在头结点，current 移动
          
    //该循环用于计算 l1 和 l2 有相同的位数的部分
    while (l1 != NULL and l2 != NULL){
    sum = l1->val + l2->val + carry;
    cur->next = new ListNode(sum%10); //取余
    carry = sum / 10; //取整，有进位是 1，否则是 0
    //向后移动
    l1 = l1->next;
    l2 = l2->next;
    cur = cur->next;
    }

    //循环结束后，判断是否还有余下的位数
    while (l1 != NULL){
    sum = l1->val + carry;
    cur->next = new ListNode(sum%10);
    carry = sum / 10;
    l1 = l1->next;
    cur = cur->next;
    }

    while (l2 != NULL){
    sum = l2->val + carry;
    cur->next = new ListNode(sum%10);
    carry = sum / 10;
    l2 = l2->next;
    cur = cur->next;
    }

    //上述循环都结束后，所有位数均已遍历，最后检查是否还有进位
    if (carry != 0){
    cur->next = new ListNode(carry);
    }

    //输出结果
    return result->next;

  • 改进

    简化了循环的过程，一次循环即可遍历两个链表的所有位

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    ListNode* head=new ListNode(-1);//存放结果的链表
    ListNode* h=head;//移动指针

    int sum=0;//每个位的加和结果
    bool carry=false;//进位标志

    // 该循环用于将 l1 和 l2 的每一位都遍历
    while(l1!=NULL||l2!=NULL){
      sum=0;
      if(l1!=NULL){
        sum+=l1->val;
        l1=l1->next;
      }
      if(l2!=NULL){
        sum+=l2->val;
        l2=l2->next;
      }
      if(carry)
        sum++;
      h->next=new ListNode(sum%10);
      h=h->next;
      carry=sum>=10?true:false;
    }

    // 最后判断是否有进位
    if(carry){
      h->next=new ListNode(1);
    }

    return head->next;

  • 递归法

    将两个链表从头开始相加，每次将两个链表的当前节点以及上一次相加的进位相加，得到一个新的节点，并将这个节点的 next 指针指向下一次递归的结果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
      ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addTwoNumbersHelper(l1, l2, 0);
      }
      // 递归函数 参数包括两个链表以及上一次相加的进位，返回值是相加后的链表
      ListNode* addTwoNumbersHelper(ListNode* l1, ListNode* l2, int carry) {
        // 首先判断递归结束的条件，即两个链表都为空且进位为 0
        if (l1 == nullptr && l2 == nullptr && carry == 0) {
            return nullptr;
        }
        // 计算当前节点的值
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        // 创建一个新的节点 并取余赋值
        ListNode* node = new ListNode(sum % 10);
        // 递归，将这个节点的 next 指针指向下一次递归的结果
        node->next = addTwoNumbersHelper(l1 ? l1->next : nullptr, l2 ? l2->next : nullptr, sum / 10);
        // 返回该节点
        return node;
      }
    };

（3）知识点

  • 错误 1：示例 3 最高位没有进位 1

    错误原因：最后检查 carry 是否为 0 时，应该是 cur->next = new ListNode(carry); 而不是 cur->next = new ListNode(sum%10);