บวกตัวเลขที่เก็บใน Linked List สองตัว ในภาษา C

ตัวเลขแต่ละหลักเก็บใน linked list (most significant digit first) บวกสอง linked list ได้ผลรวม

ตัวอย่าง

512 → 5→1→2, 14578 → 1→4→5→7→8

Result: 15090 → 1→5→0→9→0

อัลกอริทึม

1. Padding leading zeros ให้ยาวเท่ากัน
2. เดินจากท้าย (reverse iterator) บวกพร้อม carry
3. สร้าง result list โดย insert at front

โค้ดตัวอย่าง (C++ STL list)

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

list<int> addLists(list<int> l1, list<int> l2) {
    // pad zeros
    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 d:l) cout<

ผลลัพธ์
15090