C++程序针对由链表表示的两个数进行加法的-2

在上一篇中，我们介绍了通过手动对齐两个链表来进行加法的方法，并给出了相应的示例程序。但这个方法的缺点也十分明显，就是不够简洁易懂，并且要求链表长度一致，不够通用。那么，接下来我们就来讲一下另一种更加简洁易懂、对链表长度没有要求，并且还可以扩展到多个链表相加的方法。

方法2：使用C++标准库中的list

C++语言中的标准库中提供了一个list容器，该容器是双向链表的实现。利用该容器，我们可以比较方便地对链表进行操作，而不需要手动维护指针。下面是使用list容器实现链表相加的示例程序：

#include <iostream>
#include <list>

using namespace std;

// 针对由链表表示的两个数进行加法
list<int> addTwoNumbers(list<int> &l1, list<int> &l2) {
    list<int> result; // 保存结果的链表
    int carry = 0;    // 进位

    auto iter1 = l1.begin();
    auto iter2 = l2.begin();
    while (iter1 != l1.end() || iter2 != l2.end() || carry != 0) {
        int num1 = iter1 == l1.end() ? 0 : *iter1;
        int num2 = iter2 == l2.end() ? 0 : *iter2;
        int sum = num1 + num2 + carry;
        if (sum >= 10) {
            sum -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.push_back(sum);
        if (iter1 != l1.end()) {
            ++iter1;
        }
        if (iter2 != l2.end()) {
            ++iter2;
        }
    }
    return result;
}

// 输出链表
void printList(list<int> &l) {
    for (int num : l) {
        cout << num;
    }
    cout << endl;
}

int main() {
    list<int> l1 = {9, 9, 9}; // 数字999
    list<int> l2 = {5, 6, 4}; // 数字465

    printList(l1);
    cout << "+" << endl;
    printList(l2);
    cout << "=" << endl;
    list<int> result = addTwoNumbers(l1, l2);
    printList(result);

    return 0;
}

可以看到，使用list容器实现链表相加的代码非常简洁易懂，我们只需要依次遍历链表中的元素，完成相加和进位等基本操作，即可得到最终结果。需要注意的是，在遍历过程中，需要判断链表是否遍历完、链表中每个节点的值是否存在，以及进位的情况。

扩展：多个链表相加

在实际应用中，有时候我们并不仅仅需要对两个链表进行相加，还需要同时对多个链表进行相加。这时，我们可以借助前面提到的list容器来实现。下面是对于任意多个链表进行相加的示例程序：

#include <iostream>
#include <list>
#include <vector>

using namespace std;

// 针对由链表表示的任意多个数进行加法
list<int> addNumbers(vector<list<int>> &nums) {
    int carry = 0; // 进位
    list<int> result; // 保存结果的链表

    int maxLength = 0;
    for (list<int> &num : nums) {
        maxLength = max(maxLength, (int)num.size());
    }

    for (int i = 0; i < maxLength || carry != 0; ++i) {
        int sum =carry;
        for (list<int> &num : nums) {
            auto iter = num.begin();
            advance(iter, i);
            int digit = iter == num.end() ? 0 : *iter;
            sum += digit;
        }
        if (sum >= 10) {
            sum -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.push_back(sum);
    }

    return result;
}

// 输出链表
void printList(list<int> &l) {
    for (int num : l) {
        cout << num;
    }
    cout << endl;
}

int main() {
    list<int> l1 = {9, 9, 9}; // 数字999
    list<int> l2 = {5, 6, 4}; // 数字465
    list<int> l3 = {2, 3, 4, 5}; // 数字5432

    vector<list<int>> nums = {l1, l2, l3};

    for (list<int> &num : nums) {
        printList(num);
        cout << "+";
    }
    cout << endl;
    list<int> result = addNumbers(nums);
    printList(result);

    return 0;
}

可以看到，对于任意多个链表进行加法的代码也非常简洁易懂。我们只需要依次遍历每个链表中的元素并相加，同时处理进位的情况，即可得到最终结果。