链表【两数相加】具体思路——【递归】【迭代】【暴力】（附完整代码）

文章目录

• 前言
• 一、问题引入，如何理解【链表】两数相加？
• 二、方法一（固定数组暴力）
• 三、方法二（递归法）
• 四、方法三（迭代法）

前言

本文将介绍【链表】两数相加

对于这一问题将采用多种思路方法来解决

【暴力】【递归法】【迭代法】

一、问题引入，如何理解【链表】两数相加？

题目链接: [点击跳转] Leetcode 2. 两数相加

题目如下：

给出两个链表，两链表分别表示两个逆序整数，计算两整数之和，并输出所对应的逆序链表。

那么，根据题目，我们发现在代码实现时需要注意以下内容：

1.给出的两个链表为非空链表，但可能均只有一个节点0。

2.给出的两个链表的长度可能相同，也可能不同。

3.本题所给链表的节点数不超过100。

二、方法一（固定数组暴力）

对于本题而言，我们将其逻辑理解为：将两链表所表示的数，加和，然后输出为链表。

因此，我们可以考虑如何将两链表里各个节点的元素取出，并按逆序排列成真正的数。

如下：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* tre=new ListNode(0);
        int a[100]={0};
        int b[100]={0};
        ListNode* pre=tre;
        if(l1==nullptr&&l2==nullptr){
            return nullptr;
        }
        for(int i=0;l1!=nullptr;i++){
            a[i]=l1->val;
            l1=l1->next;
        }
        for(int j=0;l2!=nullptr;j++){
            b[j]=l2->val; 
            l2=l2->next; 
        }
    }
};

在这一步中，我们成功地将链表里的数导入到数组中。

（这里我们直接定义的是固定数组，因为我们提前已知了节点数的范围不会超过100。）

接下来，我们需要实现两数相加。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> sum;//计算加和
        int a[100]={0};
        int b[100]={0};
        int s=0;
        ListNode* pre=tre;
        if(l1==nullptr&&l2==nullptr){//排除空节点干扰
            return nullptr;
        }
        for(int i=0;l1!=nullptr;i++){
            a[i]=l1->val;
            l1=l1->next;
        }
        for(int j=0;l2!=nullptr;j++){
            b[j]=l2->val; 
            l2=l2->next; 
        }
        for(int x=0;x<100;x++){//求sum
            if(a[x]+b[x]<10){//如果同一位上的两个数相加<10，则无需进位
                sum.push_back(a[x]+b[x]);
            }else{//进位，下一位+1
                sum.push_back(a[x]+b[x]-10);
                a[x+1]+=1;
            }
        }
};

最后我们将得到的这个向量sum按照链表逆序输出即可。

注意：这里的节点数范围在[0,100]，因此我们不得不用vector来存储两数之和，不可以用long long类型来储存，否则会超出long long范围。

完整代码如下：

/**
 * 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* tre=new ListNode(0);
        vector<int> sum;
        int a[100]={0};
        int b[100]={0};
        int s=0;
        ListNode* pre=tre;
        if(l1==nullptr&&l2==nullptr){
            return nullptr;
        }
        for(int i=0;l1!=nullptr;i++){
            a[i]=l1->val;
            l1=l1->next;
        }
        for(int j=0;l2!=nullptr;j++){
            b[j]=l2->val; 
            l2=l2->next; 
        }
        for(int x=0;x<100;x++){//求sum
            if(a[x]+b[x]<10){
                sum.push_back(a[x]+b[x]);
            }else{
                sum.push_back(a[x]+b[x]-10);
                a[x+1]+=1;
            }
        }
        while (!sum.empty() && sum.back() == 0) {
            sum.pop_back();
        }
        if(sum.empty()){
            return tre;
        }
        while(!sum.empty()) {
            int m = sum.front();
            pre->next = new ListNode(m);
            pre = pre->next;
            sum.erase(sum.begin());
        }
        return tre->next;

    }
};

三、方法二（递归法）

在使用暴力的方法定义固定数组后，我们发现在面对节点数很少的节点，我们会无意义地将整个数组遍历出来，并且最后还需要将多余的0去除。

那么我们可不可以想到更好的方法呢？

在这里，我们可以尝试一下高贵的递归法。

首先，我们需要考虑递归的内容，很清晰：我们需要将两个链表对应元素都需要相加。

那么我们就可以明确递归的内容了，输入两节点，计算节点值之和并记录下来。

代码如下：

class Solution {
public:
    ListNode* tre = new ListNode(0);
    void addnode(ListNode* l1, ListNode* l2, int carry) {
        if (l1 == nullptr && l2 == nullptr && carry == 0) return;
        int val = (l1? l1->val : 0) + (l2? l2->val : 0) + carry;
        ListNode* newNode = new ListNode(val%10);//保证传入节点的值小于10
        ListNode* current = tre;
        while (current->next!= nullptr) {//循环找到尾节点
            current = current->next;
        }
        current->next = newNode;// 将新节点连接到结果链表上
        addnode(l1?l1->next:nullptr,l2?l2->next:nullptr,val/10);//递归，传入进位
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        addnode(l1, l2, 0);
        return tre->next;
    }
};

首先在主函数addTwoNumber传进来所给的两个链表头节点。

然后我们将这两个节点扔进我们的递归函数addnode中，同时传进一个carry，这个carry表示进位，如果传入0，表示无需进位，传入1，表示进1位。在第一次进入递归函数时，初始化为0。

并且需要在递归函数中创建节点，同时连接节点，最后递归函数结束后，链表也就完成啦！

四、方法三（迭代法）

经过上述两种方法后，我们发现，在方法一中无需使用递归函数，方法二中对于节点值的处理更加简单。我们可以尝试将两者的优点集中起来。

我们可以继续沿用carry来帮助我们计算进位，同时直接在while循环中创建节点并连接成链表。

代码如下：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode();
        ListNode* cur = head;//用cur来操作链表
        int carry = 0;//表示进位
        while (l1 || l2 || carry) {//全为0才跳出循环
            int sum = (l1? l1->val : 0) + (l2? l2->val : 0) + carry;//计算和
            cur->next = new ListNode(sum % 10);//新建节点，并连接
            carry = sum/10;//计算是否进位
            cur = cur->next;//移向下一个
            l1 = l1? l1->next : nullptr;//判断并移动
            l2 = l2? l2->next : nullptr;
        }
        return head->next;
    }
};

需要注意的是，当l1，l2，carry全为0，说明后续无数，并且不会继续向前进位，这时我们才完成了所有计算。