A+B Problem

题解+思路

题解

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *prev;
    Node *next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

Node *createList(int num)
{
    Node *head = nullptr;
    Node *tail = nullptr;
    while (num > 0)
    {
        int digit = num % 10;
        Node *newNode = new Node(digit);
        if (head == nullptr)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        num /= 10;
    }
    return head;
}

Node *addTwoNumbers(Node *num1, Node *num2)
{
    Node *result = nullptr;
    Node *current = nullptr;
    int carry = 0;

    while (num1 != nullptr || num2 != nullptr || carry != 0)
    {
        int sum = carry;

        if (num1 != nullptr)
        {
            sum += num1->data;
            num1 = num1->next;
        }

        if (num2 != nullptr)
        {
            sum += num2->data;
            num2 = num2->next;
        }

        carry = sum / 10;
        sum %= 10;

        Node *newNode = new Node(sum);

        if (result == nullptr)
        {
            result = newNode;
            current = newNode;
        }
        else
        {
            current->prev = newNode;
            newNode->next = current;
            current = newNode;
        }
    }

    return result;
}

void printList(Node *head)
{
    if (head == nullptr)
    {
        cout << "Empty list" << endl;
        return;
    }

    while (head != nullptr)
    {
        cout << head->data;
        head = head->next;
    }
    cout << endl;
}

void deleteList(Node *head)
{
    while (head != nullptr)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
}

int main()
{
    int num1 = 12345;
    int num2 = 6789;

    Node *list1 = createList(num1);
    Node *list2 = createList(num2);

    cout << "Number 1: ";
    printList(list1);

    cout << "Number 2: ";
    printList(list2);

    Node *sumList = addTwoNumbers(list1, list2);

    cout << "Sum: ";
    printList(sumList);

    deleteList(list1);
    deleteList(list2);
    deleteList(sumList);

    return 0;
}

思路

1. 首先，定义一个双向链表的节点结构体，包含一个整数值和两个指针，分别指向前一个节点和后一个节点。
2. 创建两个双向链表，分别表示要相加的两个数字。可以通过遍历输入的整数，从个位开始，逐个创建节点并将其插入链表中。
3. 定义一个变量来表示进位，初始值为0。
4. 从链表的最后一个节点开始，逐位相加，并将结果存储在新的链表中。具体步骤如下： - 从两个链表的最后一个节点开始，分别取出对应的值，并加上进位。 - 将相加的结果对10取模得到当前位的值，同时更新进位为相加结果除以10的商。 - 创建一个新的节点，将当前位的值存储在该节点中，并将该节点插入到结果链表的头部。 - 分别将两个链表的指针指向上一个节点，继续下一位的相加操作。 - 如果其中一个链表已经遍历完，但另一个链表还有剩余位数，则将剩余位数与进位相加，并将结果插入到结果链表中
5. 最后，得到的结果链表即为相加后的结果。