127 lines
3.5 KiB
C++
127 lines
3.5 KiB
C++
// AddTwoNumbers.cpp : This file contains the 'main' function. Program execution begins and ends there.
|
|
//
|
|
|
|
#include <iostream>
|
|
#include <cstdio>
|
|
|
|
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) {}
|
|
|
|
void print()
|
|
{
|
|
ListNode* head = this;
|
|
while (head)
|
|
{
|
|
printf("(%d)->", head->val);
|
|
head = head->next;
|
|
}
|
|
printf("\n");
|
|
}
|
|
};
|
|
|
|
class Solution {
|
|
private:
|
|
static inline void iterate(ListNode*& l1, ListNode*& l2)
|
|
{
|
|
l1 = l1->next;
|
|
l2 = l2->next;
|
|
}
|
|
|
|
static inline void iterate(ListNode*& l)
|
|
{
|
|
l = l->next;
|
|
}
|
|
|
|
public:
|
|
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
|
|
ListNode* left = l1, *right = l2;
|
|
ListNode* toRet = new ListNode();
|
|
ListNode* current = toRet, *prev = nullptr;
|
|
|
|
int carryover = 0;
|
|
|
|
short val = (left->val + right->val);
|
|
current->val = val % 10;
|
|
carryover = val >= 10 ? 1 : 0;
|
|
current->next = nullptr;
|
|
prev = current;
|
|
iterate(current);
|
|
|
|
iterate(left, right);
|
|
|
|
while (true)
|
|
{
|
|
if (left && right)
|
|
{
|
|
short val = (carryover + left->val + right->val);
|
|
carryover = val >= 10 ? 1 : 0;
|
|
current = new ListNode(val % 10, nullptr);
|
|
prev->next = current;
|
|
prev = current;
|
|
iterate(current);
|
|
|
|
iterate(left, right);
|
|
}
|
|
else if (left || right)
|
|
{
|
|
ListNode** toAdd = left ? &left : &right;
|
|
while (*toAdd)
|
|
{
|
|
short val = (carryover + (*toAdd)->val);
|
|
carryover = val >= 10 ? 1 : 0;
|
|
current = new ListNode(val % 10, nullptr);
|
|
|
|
prev->next = current;
|
|
prev = current;
|
|
iterate(current);
|
|
|
|
iterate(*toAdd);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (carryover)
|
|
{
|
|
current = new ListNode(1, nullptr);
|
|
|
|
prev->next = current;
|
|
prev = current;
|
|
iterate(current);
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
|
|
return toRet;
|
|
}
|
|
};
|
|
|
|
int main()
|
|
{
|
|
ListNode num1(9, new ListNode(9, nullptr)); // 32
|
|
ListNode num2(9, new ListNode(9, new ListNode(9, nullptr))); // 54
|
|
|
|
num1.print();
|
|
num2.print();
|
|
|
|
Solution s;
|
|
s.addTwoNumbers(&num1, &num2)->print();
|
|
|
|
return 0;
|
|
}
|
|
|
|
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
|
|
// Debug program: F5 or Debug > Start Debugging menu
|
|
|
|
// Tips for Getting Started:
|
|
// 1. Use the Solution Explorer window to add/manage files
|
|
// 2. Use the Team Explorer window to connect to source control
|
|
// 3. Use the Output window to see build output and other messages
|
|
// 4. Use the Error List window to view errors
|
|
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
|
|
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
|