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

给定两个由链表表示的数字，编写一个函数返回它们的和。和列表是两个输入数字的加法的链表表示。不允许修改链表。同时，不允许使用显示的额外空间（提示：使用递归）。

示例：

输入：
第一个列表：5-〉6-〉3
第二个列表：8-〉4-〉2

输出：
结果列表：1-〉4-〉0-〉5

实践

我们已经在此处讨论了一种针对链表的解决方案，其中最不重要的数字是列表的第一个节点，而最重要的数字是最后一个节点。在这个问题中，最重要的节点是第一个节点，而最不重要的数字是最后一个节点，我们不能修改这些列表。这里使用递归从右到左计算总和。

以下是步骤：

计算给定的两个链表的大小。
如果大小相同，则使用递归计算总和。在递归调用堆栈中保持所有节点直到最右边的节点，计算最右边节点的总和并向左侧转发进位。
如果大小不同，则按以下步骤进行操作：

计算两个链接列表的大小差异。让差异为 diff.
在大链表中向前移动 diff 个节点。现在使用步骤2计算较小列表和较大列表的右子列表（相同大小的子列表）的总和。还要存储这个总和的进位。
计算进位的总和（在前一步计算）与较大列表的剩余左子列表的总和。该总和的节点添加在先前步骤获取的总和列表的开头。

下面是上述方法的演示运行：

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

下面的图像实现了上述方法。

// C++递归程序，用于将两个链接列表相加
#include <bits/stdc++.h>
using namespace std;

// 链接列表节点
class Node
{
    public:
    int data;
    Node* next;
};

typedef Node node;

/* 将节点插入到链接列表的开头 */
void push(Node** head_ref, int new_data)
{
    // 分配节点
    Node* new_node = new Node[(sizeof(Node))];

    // 写入数据
    new_node->data = new_data;

    // 将旧的列表与新的节点链接
    new_node->next = (*head_ref);

    // 将头移到新节点
    (*head_ref) = new_node;
}

// 遍历和打印链接列表
void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

// 交换两个节点指针的函数
void swapPointer(Node** a, Node** b)
{
    node* t = *a;
    *a = *b;
    *b = t;
}

/* 计算链接列表的大小 */
int getSize(Node* node)
{
    int size = 0;
    while (node != NULL)
    {
        node = node->next;
        size++;
    }
    return size;
}

// 将相同大小的两个链接列表相加，分别由head1和head2表示，并返回结果的头部链接列表。当从递归返回时，进位被传播
node* addSameSize(Node* head1, Node* head2, int* carry)
{
    // 由于该函数假设链接列表的大小相同，因此检查任意两个头指针之一
    if (head1 == NULL)
        return NULL;

    int sum;

    // 分配内存给当前两个节点之和的节点
    Node* result = new Node[(sizeof(Node))];

    // 递归添加剩下的节点并取得进位
    result->next = addSameSize(head1->next, head2->next, carry);

    // 把当前两个数字和进位相加
    sum = head1->data + head2->data + *carry;
    *carry = sum / 10;
    sum = sum % 10;

    // 分配和给结果列表的当前节点
    result->data = sum;

    return result;
}

// 在较小的列表被添加到相同大小的大列表的子列表之后调用此函数。一旦右子列表被添加，就必须将进位加到较大列表的左边，以得到最终结果。
void addCarryToRemaining(Node* head1, Node* cur, int* carry, Node** result)
{
    int sum;

    // 如果未遍历相同数量的节点，则加法进位
    if (head1 != cur)
    {
        addCarryToRemaining(head1->next, cur, carry, result);

        sum = head1->data + *carry;
        *carry = sum / 10;
        sum %= 10;

        // 把这个节点添加到结果的最前面
        push(result, sum);
    }
}

// 添加由head1和head2表示的两个链接列表。两个列表的和存储在由result引用的列表中
void addList(Node* head1, Node* head2, Node** result)
{
    Node* cur;

    // 第一个列表是空的
    if (head1 == NULL)
    {
        *result =head2;
        return;
    }

    // 第二个列表是空的
    else if (head2 == NULL)
    {
        *result = head1;
        return;
    }

    int size1 = getSize(head1);
    int size2 = getSize(head2);

    int carry = 0;

    // 如果大小相等，则将相同大小的列表相加
    if (size1 == size2)
        *result = addSameSize(head1, head2, &carry);

    else
    {
        int diff = abs(size1 - size2);

        // 第一个列表应始终大于第二个列表。如果不是，则交换指针
        if (size1 < size2)
            swapPointer(&head1, &head2);

        // 遍历大的列表，这个遍历从两个列表的剩余部分开始
        for (cur = head1; diff--; cur = cur->next);

        // 现在对于两个相同大小的列表，使用函数addSameSize()来做加法
        *result = addSameSize(cur, head2, &carry);

        // 使用现有大列表的引用，加上进位数字
        addCarryToRemaining(head1, cur, &carry, result);
    }

    // 如果有进位，则将它附加到结果的第一个元素
    if (carry)
        push(result, carry);
}

// 主函数
int main()
{
    Node *head1 = NULL, *head2 = NULL, *result = NULL;

    int arr1[] = {9, 9, 9};
    int arr2[] = {1, 8};

    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    // 创建第一个链表
    int i;
    for (i = size1 - 1; i >= 0; --i)
        push(&head1, arr1[i]);

    // 创建第二个链表
    for (i = size2 - 1; i >= 0; --i)
        push(&head2, arr2[i]);

    // 添加两个列表，并要求输出结果列表
    addList(head1, head2, &result);
    printList(result);

    return 0;
}

输出：

1 0 1 7

时间复杂度:

O(m+n)，其中m和n是给定两个链表的大小。

辅助空间 ：递归调用栈占用O(m+n)的空间

迭代方法：

此实现没有任何递归调用开销，因此是迭代解决方案。

由于我们需要从两个链表的最后开始添加数字，因此这里我们将使用栈数据结构来实现它。

我们将首先从给定的两个链表中创建两个栈。
然后，我们将循环运行直到两个栈都为空。
在每次迭代中，我们跟踪进位。
最后，如果carry>0，那么这意味着我们需要在结果列表的开头额外的节点来容纳该进位。

// C++迭代程序添加两个
// 链接列表 
# include <bits/stdc++.h>
using namespace std;
   
// 链接列表节点 
class Node 
{ 
    public:
    int data; 
    Node* next; 
};
 
// 将新节点推入
// 链接列表
void push(Node** head_ref,
          int new_data) 
{ 
    // 分配节点
    Node* new_node =
          new Node[(sizeof(Node))]; 
   
    // 放入数据
    new_node->data = new_data; 
   
    // 将旧列表链接到
    // 新节点
    new_node->next = (*head_ref); 
   
    // 将头移动到指向
    // 新节点
    (*head_ref) = new_node; 
}
 
// 添加两个新数字
Node* addTwoNumList(Node* l1,
                    Node* l2)
{
    stack<int> s1,s2;
    while(l1 != NULL)
    {
        s1.push(l1->data);
        l1 = l1->next;
    }
    while(l2 != NULL)
    {
        s2.push(l2->data);
        l2 = l2->next;
    }
    int carry = 0;
    Node* result = NULL;
    while(s1.empty() == false ||
          s2.empty() == false)
    {
        int a = 0,b = 0;
        if(s1.empty() == false)
        {
            a = s1.top();
            s1.pop();
        }
        if(s2.empty() == false)
        {
            b = s2.top();
            s2.pop();
        }
        int total = a + b + carry;
        Node* temp = new Node();
        temp->data = total % 10;
        carry = total / 10;
        if(result == NULL)
        {
            result = temp;
        }
        else
        {
            temp->next = result;
            result = temp;
        }
    }
    if(carry != 0)
    {
        Node* temp = new Node();
        temp->data = carry;
        temp->next = result;
        result = temp;
    }
    return result;
}
 
// 打印链接列表
void printList(Node *node) 
{ 
    while (node != NULL) 
    { 
        cout << node->data << " "; 
        node = node->next; 
    } 
    cout < endl; 
}
 
// 驱动程序
int main() 
{ 
    Node *head1 = NULL,
         *head2 = NULL; 
   
    int arr1[] = {5, 6, 7}; 
    int arr2[] = {1, 8}; 
   
    int size1 = (sizeof(arr1) /
                 sizeof(arr1[0])); 
    int size2 = (sizeof(arr2) /
                 sizeof(arr2[0])); 
   
    // 创建第一个列表为5->6->7 
    int i; 
    for (i = size1-1; i >= 0; --i) 
        push(&head1, arr1[i]); 
   
    // 将第二个列表创建为1->8 
    for (i = size2-1; i >= 0; --i) 
        push(&head2, arr2[i]); 
     
    Node* result =
          addTwoNumList(head1, head2);
    printList(result); 
   
    return 0; 
}

输出：