Cộng 2 số biểu diễn bằng danh sách liên kết trong C++

Mỗi nút lưu 1 chữ số. Số 512 lưu: 5→1→2. Cộng 2 danh sách như cộng tay: từ cuối, nhớ.

Ví dụ

512 + 14578 = 15090

Chương trình (STL list)

#include <iostream>
#include <list>
using namespace std;

list<int> addLists(list<int> l1, list<int> l2) {
    // Cân bằng độ dài
    while (l1.size() < l2.size()) l1.push_front(0);
    while (l2.size() < l1.size()) l2.push_front(0);
    
    list<int> res;
    int carry = 0;
    
    auto it1 = l1.rbegin(), it2 = l2.rbegin();
    while (it1 != l1.rend()) {
        int sum = *it1 + *it2 + carry;
        res.push_front(sum % 10);
        carry = sum / 10;
        ++it1; ++it2;
    }
    if (carry) res.push_front(carry);
    return res;
}

list<int> toList(int n) {
    list<int> l;
    while (n) { l.push_front(n % 10); n /= 10; }
    return l;
}

void printList(list<int> l) {
    for (int x : l) cout << x;
    cout << endl;
}

int main() {
    list<int> a = toList(512);
    list<int> b = toList(14578);
    list<int> c = addLists(a, b);
    
    cout << "So 1: "; printList(a);
    cout << "So 2: "; printList(b);
    cout << "Tong: "; printList(c);
    return 0;
}

Kết quả

So 1: 512
So 2: 14578
Tong: 15090