0002.Add-Two-Numbers

两数相加

1. 题目

1.1. 描述

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

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

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

1.2. 示例

示例 1

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

示例 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.3. 提示

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

2. 思路

【大意】两个逆序链表从低位开始每位相加，结果存放于另一个逆序链表中

2.1. 迭代法

• 设置进位变量carry，构建一个带头结点的单链表ans
• l1和l2链表从头往后同时处理，每两结点相加结果加上carry的值，作为ans链表新结点值，采用尾插法插入到ans链表中
• 及时更新carry的值
• 时间复杂度为O(max(m,n))，其中 m 和 n 分别为两个链表的长度
• 空间复杂度为O(1)，返回值不计入空间复杂度

2.2. 递归法

• 设置进位变量carry，构建一个不带头结点的单链表ans
• l1和l2链表从头往后同时递归处理，需要两结点相加
  • 将进位carry值加到l1链表结点中
  • 当l1链表结点为空时，l1链表中插入一个值为0的新结点。l2链表同理
  • 当最高位carry值还为1时，l1和l2链表都插入值为0的新结点
• 时间复杂度为O(max(m,n))，其中 m 和 n 分别为两个链表的长度
• 空间复杂度为O(max(m,n))，其中 m 和 n 分别为两个链表的长度

3. 代码

3.1. C++

3.1.1. 迭代法

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ans = new ListNode(-1);
        ListNode* p = ans;
        int carry = 0;
        while(l1!= NULL||l2!=NULL||carry!=0){
            // 每一位计算的同时需要考虑上一位的进位情况
            int sum = carry;
            // 只有链表不为空时才能继续遍历
            if(l1!=NULL){
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=NULL){
                sum+=l2->val;
                l2=l2->next;
            }
            // 进位为当前计算结果的十位数
            // 如 9+9=18，个位为8，进位为1
            carry = sum/10;
            // 构建新结点用来存放值
            // 值应当是计算结果的个位数
            ListNode* s = new ListNode(sum%10);  
						// 尾插法插入结果链表
            p->next = s;
            p=s;

        }
        // 返回结果不带头结点
        return ans->next;
    }
};

3.1.2. 递归法

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum = l1->val+l2->val;
        // 构建新结点值是计算结果的个位数
        ListNode* ans = new ListNode(sum%10);
        // 进位为当前计算结果的十位数
        int carry = sum/10;

        if(l1->next!= NULL||l2->next!=NULL||carry!=0){
            // 到达尾结点，插入结点
            if(l1->next == NULL){
                l1->next = new ListNode(0);
            }
            l1=l1->next;

            if(l2->next == NULL){
                l2->next = new ListNode(0);
            }
            l2=l2->next;
            // 将进位值加到l1链表结点中
            l1->val += carry; 
						// 进入下一层遍历
            ans->next = addTwoNumbers(l1,l2);
        }
        return ans;
    }
};

3.2. Java

3.2.1. 迭代法

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ans = new ListNode(-1);
        ListNode p = ans;
        int carry = 0;
        while(l1!=null||l2!=null||carry!=0){
            int sum = carry;
            if(l1!=null){
                sum+=l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                sum+=l2.val;
                l2=l2.next;
            }
            ListNode s = new ListNode(sum%10);
            carry = sum/10;

            p.next = s;
            p=s;
        }
        return ans.next;
    }
}

3.2.2. 递归法

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = l1.val+l2.val;
        ListNode ans = new ListNode(sum%10);
        int carry = sum/10;

        if(l1.next!=null||l2.next!=null||carry!=0){
            if(l1.next==null){
                l1.next=new ListNode(0);
            }
            l1=l1.next;

            if(l2.next==null){
                l2.next=new ListNode(0);
            }
            l2=l2.next;

            l1.val+=carry;

            ans.next = addTwoNumbers(l1,l2);
        }
        return ans;
    }
}