Add Two Numbers: carry lan truyền trên linked list đã được căn chỉnh sẵn

Các chữ số đã được sắp xếp đúng thứ tự rồi. Đó là điều mà hầu hết mọi người bỏ qua khi đọc đề lần đầu. Bạn nhận được l1 = [2, 4, 3] đại diện cho 342 — chữ số hàng đơn vị đứng trước — và l2 = [5, 6, 4] đại diện cho 465. Phép cộng theo kiểu trường học bắt đầu từ cột đơn vị và đi từ phải sang trái. Hai linked list đã được căn chỉnh theo cách đó rồi. Bạn đi song song qua cả hai list từ đầu đến cuối, cộng từng cặp, theo dõi carry. Xong.

Câu hỏi thú vị không phải là "giải bài này thế nào" mà là "liệu tôi có cần chuyển sang integer trước không, và nếu làm vậy thì điều gì sẽ bị vỡ?"

Đề bài

Cho hai linked list không rỗng đại diện cho hai số nguyên không âm. Các chữ số được lưu theo thứ tự ngược — chữ số hàng đơn vị ở đầu list — và mỗi node chứa đúng một chữ số. Cộng hai số và trả về tổng dưới dạng linked list theo cùng định dạng. Đề gốc: LeetCode 2.

Ràng buộc:
- Số lượng node trong mỗi linked list nằm trong khoảng [1, 100].
- 0 <= Node.val <= 9
- Đảm bảo rằng list biểu diễn một số không có leading zero.

Constraints bắt buộc điều gì

[1, 100] node mỗi list. 0 <= Node.val <= 9. Không có leading zero trừ số 0.

Giới hạn trên 100 node nghĩa là mỗi list có thể đại diện cho một số lên đến 100 chữ số. Số đó có thể cực kỳ lớn theo giá trị tuyệt đối — 10^100 vượt xa long trong C# (tối đa khoảng 9.2 * 10^18) và Python's native int (Python dùng arbitrary-precision nên tránh được overflow, nhưng C# thì không). Nếu bạn chuyển sang integer trong C# mà không dùng BigInteger, bạn sẽ gặp overflow âm thầm. Constraint này được chọn chủ ý để làm phép tính integer naive trở nên rủi ro.

Tối thiểu 1 node mỗi list cũng có ý nghĩa: cả hai list không bao giờ là null. Bạn không cần null-check trước vòng lặp đầu tiên. Điều kiện vòng lặp vẫn phải xử lý trường hợp hai list có độ dài khác nhau — một list cạn kiệt trước list kia — nhưng không có trường hợp list rỗng.

Không có leading zero (trừ [0]) nghĩa là số 5 được biểu diễn là [5] chứ không phải [5, 0, 0]. List kết quả cũng có tính chất tương tự: bài toán đảm bảo output không có leading zero. Bạn không cần cắt bỏ kết quả.

Approach 1: chuyển sang integer, cộng, chuyển ngược lại

Bản năng brute-force là trích xuất cả hai số, cộng chúng lại, rồi tái tạo lại linked list. Duyệt qua l1 tích lũy các chữ số theo vị trí, làm tương tự với l2, cộng lại, rồi tách từng chữ số từ tổng bằng modulo.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def list_to_number(node):
            num = 0
            multiplier = 1
            while node:
                num += node.val * multiplier
                multiplier *= 10
                node = node.next
            return num
 
        def number_to_list(num):
            if num == 0:
                return ListNode(0)
            dummy = ListNode(0)
            cur = dummy
            while num > 0:
                cur.next = ListNode(num % 10)
                cur = cur.next
                num //= 10
            return dummy.next
 
        return number_to_list(list_to_number(l1) + list_to_number(l2))

using System.Numerics;
 
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
 
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        BigInteger ListToNumber(ListNode node) {
            BigInteger num = 0;
            BigInteger multiplier = 1;
            while (node != null) {
                num += node.val * multiplier;
                multiplier *= 10;
                node = node.next;
            }
            return num;
        }
 
        ListNode NumberToList(BigInteger num) {
            if (num == 0) return new ListNode(0);
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;
            while (num > 0) {
                cur.next = new ListNode((int)(num % 10));
                cur = cur.next;
                num /= 10;
            }
            return dummy.next;
        }
 
        BigInteger n1 = ListToNumber(l1);
        BigInteger n2 = ListToNumber(l2);
        return NumberToList(n1 + n2);
    }
}

Phiên bản Python hoạt động ổn với arbitrary-precision integer. Phiên bản C# cần BigInteger — nếu không dùng nó, bạn sẽ bị overflow với input trên 18 chữ số mỗi list. Time là O(max(m, n)): hai lần duyệt để trích xuất, một lần để xây dựng kết quả. Space là O(max(m, n)) cho result list; Python còn dùng O(digits) nội bộ cho big integer, nhưng điều đó bị output chi phối dù sao.

Approach chuyển đổi này tạo ra hai lần duyệt thêm trên dữ liệu mà không có lợi ích tiệm cận nào. Nó còn mang theo rủi ro overflow trong C#. Tôi sẽ không dùng nó trong code production hay trong phỏng vấn khi interviewer hỏi "nếu các list rất dài thì sao?"

Approach 2: simulation carry từng chữ số một

Duyệt song song cả hai list. Tại mỗi vị trí, cộng hai giá trị chữ số cộng với carry từ vị trí trước. Chữ số mới là total % 10, carry mới là total // 10. Tạo một result node, tiến tất cả ba con trỏ, lặp lại cho đến khi cả hai list cạn và carry bằng không.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        carry = 0
 
        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
 
            total = val1 + val2 + carry
            carry = total // 10
 
            cur.next = ListNode(total % 10)
            cur = cur.next
 
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
 
        return dummy.next

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
 
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;
 
            int total = val1 + val2 + carry;
            carry = total / 10;
 
            cur.next = new ListNode(total % 10);
            cur = cur.next;
 
            l1 = l1?.next;
            l2 = l2?.next;
        }
 
        return dummy.next;
    }
}

carry là int trong C# — hai chữ số đơn cộng với carry đến tối đa là 1 cho tổng tối đa là 19, nằm trong phạm vi int. Không cần BigInteger. Phép tính per-position không bao giờ overflow vì bạn không bao giờ tái tạo lại số đầy đủ.

Dummy node tránh trường hợp đặc biệt của node đầu tiên. Nếu không có nó, bạn cần phát hiện "đây có phải lần lặp đầu tiên không" và xử lý head = new ListNode(...) riêng biệt. Dummy hấp thụ boilerplate đó: cur = dummy, cur.next = new ListNode(...), tiến cur. Cuối cùng, dummy.next là head thực sự.

Trace từng bước carry: [2,4,3] + [5,6,4]

Vị trí 1 (hàng đơn vị): 2 + 5 + 0 = 7. Chữ số 7, carry 0. Kết quả đến nay: [7].

Vị trí 2 (hàng chục): 4 + 6 + 0 = 10. Chữ số 0, carry 1. Kết quả đến nay: [7, 0].

Vị trí 3 (hàng trăm): 3 + 4 + 1 = 8. Chữ số 8, carry 0. Kết quả đến nay: [7, 0, 8].

Cả hai list đã cạn, carry bằng 0. Xong. Đáp án: [7, 0, 8] đại diện cho 807 = 342 + 465.

Bây giờ xét ví dụ khó hơn từ constraints: [9,9,9,9,9,9,9] (9,999,999) + [9,9,9,9] (9,999).

Vị trí 1-4: mỗi vị trí tính 9 + 9 + carry. Vị trí đầu: 9 + 9 + 0 = 18, chữ số 8, carry 1. Vị trí 2-4: 9 + 9 + 1 = 19, chữ số 9, carry 1. Sau bốn vị trí, kết quả là [8,9,9,9] và carry là 1.

Vị trí 5-7: l2 đã cạn, nên val2 = 0. Mỗi vị trí là 9 + 0 + 1 = 10, chữ số 0, carry 1. Sau ba vị trí này, kết quả là [8,9,9,9,0,0,0] và carry là 1.

Cả hai list đã cạn, nhưng carry vẫn là 1. Vòng lặp chạy thêm một lần nữa: val1 = 0, val2 = 0, total = 0 + 0 + 1 = 1, chữ số 1, carry 0. Kết quả: [8,9,9,9,0,0,0,1]. Khớp với output mong đợi.

Time và space

Time: O(max(m, n)). Bạn lặp cho đến khi cả hai list cạn và carry bằng không. Kết quả có tối đa max(m, n) + 1 node — node thêm xuất hiện khi carry cuối cùng lan ra (ví dụ: [5] + [5] cho [0, 1]).

Space: O(max(m, n)) cho result list. Bộ nhớ phụ duy nhất là carry, val1, val2, và hai list pointer — O(1) extra space nếu không tính output.

Các edge case và tại sao code xử lý được chúng

Độ dài khác nhau ([1] + [9,9,9]): khi l1 cạn, val1 = 0. Vòng lặp tiếp tục chạy theo l2 và cuối cùng theo carry. Điều kiện while l1 or l2 or carry xử lý ba driver này độc lập — không có giả định nào rằng cả hai list kết thúc cùng nhau.

Carry cuối cùng ([5] + [5]): 5 + 5 = 10, chữ số 0, carry 1. Sau một lần lặp, cả hai list đều null nhưng carry = 1. Vòng lặp chạy thêm với val1 = 0, val2 = 0, emit chữ số 1. Nếu không có or carry trong điều kiện vòng lặp, node này sẽ bị bỏ sót âm thầm và kết quả sẽ là [0] thay vì [0, 1]. Đây là bug phổ biến nhất trong các implementation của bài này.

Cả hai đầu vào là số không ([0] + [0]): lần lặp đầu tiên, 0 + 0 + 0 = 0, chữ số 0, carry 0. Cả hai list trở thành null, carry bằng 0. Vòng lặp thoát. Kết quả là [0]. Đúng.

Một node với carry ([9] + [1]): 9 + 1 = 10, chữ số 0, carry 1. Cả hai list cạn sau một lần lặp. Vòng lặp tiếp tục với toàn số 0 cộng carry 1, emit chữ số 1. Kết quả: [0, 1] đại diện cho 10.

Input có độ dài tối đa (100 node mỗi list, toàn 9): cả hai số là 10^100 - 1. Tổng của chúng là 2 * 10^100 - 2, một số 101 chữ số. Simulation xử lý điều này tự nhiên — 100 lần lặp mỗi lần tạo ra một chữ số, cộng với một lần lặp carry cuối cùng tạo ra chữ số đứng đầu. Không có kiểu integer nào có thể giữ số này trong C# một cách native, xác nhận rằng approach chuyển đổi không dùng BigInteger sẽ fail âm thầm ở quy mô này.

Bảng so sánh

Cả hai approach chạy trong cùng time và space tiệm cận. Approach simulation không có rủi ro overflow trong bất kỳ ngôn ngữ nào, xử lý số chữ số bất kỳ, và không phức tạp hơn đáng kể để viết. Không có sự đánh đổi thực sự ở đây. Tôi sẽ chọn simulation.

Pattern cơ bản và nơi nó xuất hiện lại

Bài toán này là carry propagation kết hợp với dummy-head construction pattern. Cả hai đều là nền tảng.

Carry propagation: bất kỳ phép toán số học nào trên chuỗi chữ số — cộng, trừ, nhân — đều cần theo dõi một giá trị chảy sang vị trí tiếp theo. Cấu trúc linked list ở đây chỉ là ngẫu nhiên; cùng pattern đó xuất hiện trong "Add to Array-Form of Integer" (LeetCode 989) và "Add Binary" (67) trên array và string. Implementation luôn là: total = a + b + carry, digit = total % base, carry = total / base.

Dummy-head construction: khi bạn đang xây dựng một linked list mới mà head chưa biết trước, tạo một sentinel node trước vòng lặp, gắn các node vào sentinel.next, tiến con trỏ cur, và trả về sentinel.next ở cuối. Pattern này loại bỏ câu hỏi "head là gì?" và giữ cho phần thân vòng lặp đồng nhất. Nó xuất hiện trong Merge Two Sorted Lists, Reorder List, và hầu hết mọi bài toán yêu cầu xây dựng một linked list.

Vị trí trong series linked list

Series đến nay đã bao gồm Reverse Linked List (206), Merge Two Sorted Lists (21), và Reorder List (143). Những bài đó đã thiết lập pointer manipulation, tái cấu trúc in-place, và pattern two-pointer traversal.

Add Two Numbers là bài đầu tiên trong series vận hành trên hai input list và yêu cầu arithmetic thay vì tái cấu trúc. Đó là bước nhảy khái niệm: bạn không sắp xếp lại pointer — bạn đọc giá trị, tính toán, và ghi vào một list mới.

Add Two Numbers II (445) là phần tiếp theo trực tiếp. Các chữ số được lưu theo thứ tự xuôi (có nghĩa quan trọng nhất đứng trước), vì vậy bạn không thể simulation từ trái sang phải mà không đảo ngược các list trước hoặc dùng stack để trì hoãn việc trích xuất chữ số. Thuật toán giống nhau; setup khó hơn.

Add to Array-Form of Integer (989) là phiên bản array của bài này: một số được lưu dưới dạng digit array cộng với một scalar integer. Cùng carry propagation; cấu trúc dữ liệu khác.

Multiply Strings (43) tổng quát hóa từ phép cộng sang phép nhân. Logic carry phức tạp hơn (tích lũy partial product theo từng vị trí), nhưng pattern xử lý digit-by-digit vào result array về tinh thần là giống nhau.

Add Binary (67) là bài toán tương tự trên cơ số 2 theo dạng string. Nếu bạn hiểu pattern carry propagation ở đây, Add Binary chỉ khác một hằng số (% 2, // 2 thay vì % 10, // 10).