#include
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;

}