Skip to content

Instantly share code, notes, and snippets.

@starwing
Last active January 8, 2020 03:55
Show Gist options
  • Save starwing/2e2885d3d227a57860b13ea57707dc3d to your computer and use it in GitHub Desktop.
Save starwing/2e2885d3d227a57860b13ea57707dc3d to your computer and use it in GitHub Desktop.
Linked List addition in C++
#include <string>
class List {
struct Node {
Node* next;
int val;
Node(int val, Node* next = nullptr)
: next(next), val(val) {}
};
Node* head_;
explicit List(Node* head) : head_(head) {}
public:
List() : head_(nullptr) {}
~List() {
while (head_) {
Node* next = head_->next;
delete head_;
head_ = next;
}
}
explicit List(const char* n) : head_(nullptr) {
for (; *n != '\0'; ++n) {
assert(*n >= '0' && *n <= '9');
push(*n - '0');
}
}
List& push(int n) {
head_ = new Node(n, head_);
return *this;
}
std::string to_string() const {
std::string r;
for (Node* p = head_; p; p = p->next)
r += static_cast<char>(p->val + '0');
std::reverse(r.begin(), r.end());
return r;
}
List operator+(List const& b) const {
Node *prev = nullptr, *l = head_, *r = b.head_;
List ret;
int carry = 0;
for (; l && r; l = l->next, r = r->next)
ret.append_carry(prev, carry += l->val + r->val);
for (; l; l = l->next)
ret.append_carry(prev, carry += l->val);
for (; r; r = r->next)
ret.append_carry(prev, carry += r->val);
while (carry)
ret.append_carry(prev, carry);
return ret;
}
private:
const static int RADIX = 10;
void append_carry(Node*& prev, int& carry) {
Node* n = new Node(carry % RADIX);
carry /= RADIX;
if (prev != nullptr) prev->next = n;
if (head_ == nullptr) head_ = prev;
prev = n;
}
};
#include <iostream>
int main(void)
{
std::cout << (List("123") + List("456")).to_string() << std::endl;
std::cout << (List("123000") + List("456")).to_string() << std::endl;
std::cout << (List("123") + List("456000")).to_string() << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment