Cộng hai số II (Linked List) trong C++

Mô tả bài toán

Cho 2 danh sách liên kết biểu diễn số không âm (chữ số quan trọng nhất ở đầu). Cộng hai số, trả về danh sách liên kết kết quả.

Ví dụ: [7,2,4,3] + [5,6,4] = [7,8,0,7] (7243 + 564 = 7807).

Giải thuật Stack

1. Đẩy tất cả nút của 2 danh sách vào 2 stack s1, s2.
2. Pop từng cặp, cộng có nhớ (sum).
3. Tạo nút mới cho chữ số sum % 10, chèn vào đầu danh sách kết quả (head insertion).
4. Cập nhật sum /= 10.
5. Cuối cùng nếu còn nhớ, tạo nút thêm.

Cài đặt C++

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

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

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    ListNode* cur = head;
    for (int i = 1; i < v.size(); i++) {
        cur->next = new ListNode(v[i]);
        cur = cur->next;
    }
    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) {
        stack<ListNode*> s1, s2;
        while (l1) { s1.push(l1); l1 = l1->next; }
        while (l2) { s2.push(l2); l2 = l2->next; }
        int sum = 0;
        ListNode* dummy = new ListNode(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* node = new ListNode(sum / 10);
            node->next = dummy;
            dummy = node;
            sum /= 10;
        }
        return dummy->val == 0 ? dummy->next : dummy;
    }
};

int main() {
    ListNode* l1 = make_list({7,2,4,3});
    ListNode* l2 = make_list({5,6,4});
    Solution ob;
    print_list(ob.addTwoNumbers(l1, l2)); // [7, 8, 0, 7]
    return 0;
}

Độ phức tạp

• Thời gian: O(max(m,n)).
• Không gian: O(max(m,n)) cho 2 stack.