Giới thiệu

Nếu bạn đã từng chuẩn bị cho các cuộc phỏng vấn kỹ thuật, chắc chắn bạn đã gặp bài toán "Cộng Hai Số" trên LeetCode. Đây là một bài toán kinh điển, thường xuyên được các công ty công nghệ hàng đầu yêu cầu, vì nó kiểm tra khả năng hiểu biết của bạn về đệ quy, danh sách liên kết và logic toán học cơ bản.

Trong bài viết này, chúng ta sẽ phân tích bài toán này từng bước một. Chúng ta sẽ không chỉ xem xét một giải pháp mà là hai phương pháp mạnh mẽ: một phương pháp lặp đơn giản và một phương pháp đệ quy thanh lịch.

Phân Tích Vấn Đề

Trước tiên, hãy hiểu nhiệm vụ. Chúng ta có hai danh sách liên kết không rỗng, mỗi nút chứa một chữ số. Các chữ số được lưu trữ theo thứ tự ngược lại. Nhiệm vụ của chúng ta là cộng hai số này lại với nhau và trả về kết quả dưới dạng danh sách liên kết mới.

Ví dụ, nếu đầu vào là l1 = [2,4,3] và l2 = [5,6,4], điều này đại diện cho các số 342 và 465. Tổng là 807, và chúng ta cần trả về danh sách liên kết [7,0,8].

Thách Thức Chính

Các thách thức chính ở đây là:

Duyệt qua cả hai danh sách liên kết đồng thời.
Xử lý các trường hợp một danh sách dài hơn danh sách kia.
Tính toán và quản lý giá trị carry một cách chính xác ở mỗi bước.
Xây dựng danh sách liên kết kết quả mới trong quá trình thực hiện.

Giải Pháp 1: Phương Pháp Lặp (Phương Pháp Chính)

Cách đơn giản nhất để giải quyết là sử dụng vòng lặp while. Chúng ta sẽ lặp qua các danh sách miễn là còn chữ số trong l1 hoặc l2, hoặc nếu còn một carry từ phép tính trước đó.

Một mẫu phổ biến và rất hữu ích ở đây là sử dụng một dummyNode. Nút này đóng vai trò là một placeholder cho đầu danh sách mới của chúng ta, giúp đơn giản hóa mã nguồn và không cần xử lý nút đầu tiên như một trường hợp đặc biệt.

Mã Giải Pháp Lặp Trong Python

python Copy

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummyNode = ListNode(0)
        current = dummyNode
        carry = 0

        while l1 or l2 or carry != 0:
            # Lấy giá trị, sử dụng 0 nếu danh sách bị cạn kiệt
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # Thực hiện phép cộng
            total_sum = val1 + val2 + carry
            carry = total_sum // 10
            digit = total_sum % 10

            # Tạo nút mới và di chuyển con trỏ của chúng ta
            current.next = ListNode(digit)
            current = current.next

            # Tiến lên các con trỏ danh sách
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummyNode.next

Giải Thích Giải Pháp Lặp

Khởi Tạo: Chúng ta tạo một dummyNode để neo danh sách kết quả và một con trỏ current để xây dựng nó. carry bắt đầu bằng 0.
Vòng Lặp: Vòng lặp tiếp tục miễn là l1, l2 hoặc carry có giá trị. Điều này xử lý một cách thanh lịch các độ dài danh sách khác nhau và carry cuối cùng (như trong 9 + 9 = 18).
Trích Xuất Giá Trị: val1 = l1.val if l1 else 0 là một cách sạch để xử lý một danh sách dài hơn danh sách kia. Nếu một danh sách là None, chúng ta chỉ cần sử dụng 0 cho phép tính.
Xây Dựng Kết Quả: Chúng ta tạo một ListNode mới với chữ số đã tính toán và gắn nó vào danh sách kết quả.
Giá Trị Trả Về: Chúng ta trả về dummyNode.next, là đầu thật sự của danh sách mới.

Giải Pháp 2: Phương Pháp Đệ Quy (Phương Pháp Thanh Lịch)

Đệ quy thường dẫn đến mã ngắn gọn và rõ ràng hơn. Bài toán có thể được diễn đạt lại một cách đệ quy:

Tổng của hai danh sách liên kết là một nút mới với tổng của các chữ số hiện tại, mà con trỏ tiếp theo là tổng của phần còn lại của các danh sách.

Điều này hoàn toàn phù hợp với một hàm đệ quy.

Mã Giải Pháp Đệ Quy

python Copy

class Solution(object):
    def addTwoNumbers(self, l1, l2, carry=0):
        # Trường Hợp Cơ Bản: dừng lại khi không còn nút nào và không còn carry
        if not l1 and not l2 and not carry:
            return None

        # Lấy giá trị, sử dụng 0 nếu nút là None
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Thực hiện phép cộng
        total_sum = val1 + val2 + carry
        carry = total_sum // 10
        digit = total_sum % 10

        # Tạo nút mới cho chữ số hiện tại
        newNode = ListNode(digit)

        # Bước Đệ Quy: gọi hàm cho các nút tiếp theo
        next_l1 = l1.next if l1 else None
        next_l2 = l2.next if l2 else None
        newNode.next = self.addTwoNumbers(next_l1, next_l2, carry)

        return newNode

Giải Thích Giải Pháp Đệ Quy

Trường Hợp Cơ Bản: Đệ quy dừng lại khi cả hai danh sách đều cạn kiệt (None) và không còn carry để thêm. Đây là phần quan trọng nhất của bất kỳ giải pháp đệ quy nào.
Bước Đệ Quy: Đối với mỗi lần gọi, chúng ta tính toán tổng và chữ số giống như trong phiên bản lặp. Chúng ta tạo một newNode với chữ số này. Điều kỳ diệu xảy ra tiếp theo: chúng ta đặt newNode.next bằng kết quả của việc gọi hàm một lần nữa với các nút tiếp theo và carry mới.

So Sánh Các Phương Pháp

Thời Gian Phức Tạp là giống nhau (O(n)) cho cả hai vì chúng ta phải truy cập từng nút trong danh sách dài hơn ít nhất một lần.

Không Gian Phức Tạp là sự khác biệt chính. Giải pháp lặp sử dụng một không gian phụ hằng số (O(1)) cho các biến dummyNode, current và carry. Giải pháp đệ quy, tuy nhiên, tạo ra một khung ngăn xếp mới cho mỗi lần gọi, vì vậy không gian (O(n)) mà nó sử dụng tỷ lệ thuận với độ dài của danh sách dài nhất. Đối với những danh sách rất lớn, điều này có thể lý thuyết dẫn đến lỗi tràn ngăn xếp.

Kết Luận

Bài toán Cộng Hai Số là một bài tập tuyệt vời để làm chủ đệ quy và manipulation danh sách liên kết. Bằng cách triển khai cả một giải pháp lặp và một giải pháp đệ quy, chúng ta có thể đánh giá các cách tiếp cận khác nhau cho cùng một vấn đề và hiểu những ưu nhược điểm độc đáo của chúng về không gian và khả năng đọc.

Bạn thích giải pháp nào hơn? Hãy cho tôi biết trong phần bình luận! Chúc bạn lập trình vui vẻ.

Giải Quyết Vấn Đề "Cộng Hai Số" Trong LeetCode: Phương Pháp Lặp và Đệ Quy