Làm thế nào để cộng hai số lớn được biểu diễn dưới dạng hai Danh sách liên kết đơn (Add Two Numbers), trong đó các chữ số được lưu trữ theo thứ tự ngược lại?

Question

Accepted Answer

Bản chất bài toán
Bài toán yêu cầu cộng hai số nguyên không giới hạn kích thước (được lưu trữ dưới dạng Linked Lists ngược, tức là node đầu tiên chứa chữ số hàng đơn vị). Yêu cầu này tương tự như việc thực hiện phép cộng cột dọc thủ công, đòi hỏi phải xử lý biến nhớ (carry) từ hàng thấp lên hàng cao.
Thuật toán giải quyết

Khởi tạo một Dummy Head để dễ dàng xây dựng danh sách kết quả.
Duy trì biến carry khởi tạo bằng 0.
Sử dụng vòng lặp duyệt qua cả hai danh sách cho đến khi cả hai danh sách đều cạn và carry bằng 0.
Tại mỗi bước, lấy giá trị của node hiện tại (nếu tồn tại), cộng với carry và giá trị từ danh sách kia.
Cập nhật carry = sum / 10 và giá trị node mới là sum % 10.
Chuyển dịch con trỏ sang các node tiếp theo.

Ví dụ mã nguồn minh họa (Java)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode current = dummyHead;
    int carry = 0;

while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }

carry = sum / 10;
        current.next = new ListNode(sum % 10);
        current = current.next;
    }

return dummyHead.next;
}
Độ phức tạp

Thời gian (Time Complexity): O(max(N, M)) với N và M là số lượng node của hai danh sách.
Không gian (Space Complexity): O(max(N, M)) để lưu trữ danh sách kết quả.

Lưu ý thực chiến Enterprise
Khi làm việc với các hệ thống tài chính xử lý số tiền lớn vượt quá kiểu dữ liệu nguyên thủy (BigInt hoặc chuỗi), việc hiểu rõ cơ chế phân bổ bộ nhớ cho danh sách liên kết giúp tránh hiện tượng tràn bộ nhớ heap khi tạo quá nhiều node mới.

Làm thế nào để cộng hai số lớn được biểu diễn dưới dạng hai Danh sách liên kết đơn (Add Two Numbers), trong đó các chữ số được lưu trữ theo thứ tự ngược lại?

Bản chất bài toán

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi linked lists liên quan cùng chủ đề