บวกเลขสองจำนวนแบบ Linked List II ใน C++

ให้ linked list สองตัว แทนจำนวนเต็มไม่ติดลบ (หลักสำคัญอยู่หน้า) ต้องบวกสองจำนวน คืนเป็น linked list ตัวอย่าง: [7,2,4,3] + [5,6,4] = [7,8,0,7]

ขั้นตอนการแก้ปัญหา (Stack)

1. สร้าง dummy node ค่า 0, สแต็ก s1, s2
2. ดึงโนดทั้งสอง list ใส่สแต็กตามลำดับ
3. sum = 0
4. วนจนสแต็กทั้งสองว่าง:
   • ถ้า s1 ไม่ว่าง pop บวกเข้า sum
   • ถ้า s2 ไม่ว่าง pop บวกเข้า sum
   • dummy->val = sum % 10
   • สร้างโนดใหม่ค่า sum/10, next = dummy, dummy = โนดใหม่
   • sum /= 10
5. ถ้า dummy->val == 0 คืน dummy->next ไปคืน dummy

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val; ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* p = head;
        while (p->next) p = p->next;
        p->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode* head) {
    cout << "[";
    while (head) { cout << head->val << ", "; head = head->next; }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        stack<ListNode*> s1, s2;
        while (l1) { s1.push(l1); l1 = l1->next; }
        while (l2) { s2.push(l2); l2 = l2->next; }
        int sum = 0;
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) { sum += s1.top()->val; s1.pop(); }
            if (!s2.empty()) { sum += s2.top()->val; s2.pop(); }
            dummy->val = sum % 10;
            ListNode* nn = new ListNode(sum / 10);
            nn->next = dummy;
            dummy = nn;
            sum /= 10;
        }
        return dummy->val == 0 ? dummy->next : dummy;
    }
};

int main() {
    vector<int> v1 = {7,2,4,3}, v2 = {5,6,4};
    Solution ob;
    print_list(ob.addTwoNumbers(make_list(v1), make_list(v2)));
}

Input

[7,2,4,3] [5,6,4]

Output

[7, 8, 0, 7, ]