Bài 2 Leetcode: Add Two Numbers

Đề bài:

Bạn được cho hai danh sách liên kết không rỗng đại diện cho hai số nguyên không âm. Các chữ số được lưu trữ theo thứ tự ngược, và mỗi nút trong danh sách chứa một chữ số duy nhất. Hãy cộng hai số này và trả về tổng dưới dạng một danh sách liên kết.

Bạn có thể giả định rằng hai số không chứa số 0 ở đầu, trừ trường hợp số 0 chính nó.

Ví dụ 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Ví dụ 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Ví dụ 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Ràng buộc:

• Số lượng nút trong mỗi danh sách liên kết nằm trong khoảng [1, 100].
• 0 <= Node.val <= 9
• Đảm bảo rằng danh sách đại diện cho một số không có số 0 dẫn đầu.

Giải thích thuật toán bằng C++

class Solution {
 public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    int carry = 0;

    while (l1 || l2 || carry) {
      if (l1 != nullptr) {
        carry += l1->val;
        l1 = l1->next;
      }
      if (l2 != nullptr) {
        carry += l2->val;
        l2 = l2->next;
      }
      curr->next = new ListNode(carry % 10);
      carry /= 10;
      curr = curr->next;
    }

    return dummy.next;
  }
};

Đoạn mã trên triển khai thuật toán để cộng hai số được biểu diễn bởi hai danh sách liên kết. Dưới đây là giải thích chi tiết về cách thuật toán hoạt động:

1. Khởi tạo một nút giả (dummy) với giá trị 0 và con trỏ curr trỏ tới nút giả này. Cũng khởi tạo một biến carry để lưu trữ giá trị nhớ ban đầu là 0.

2. Bắt đầu vòng lặp while cho đến khi cả hai danh sách liên kết l1 và l2 đều kết thúc và không có giá trị nhớ cần xử lý. Trong mỗi vòng lặp, ta thực hiện các bước sau:

a. Kiểm tra xem l1 có tồn tại hay không. Nếu có, ta cộng giá trị của l1->val với giá trị nhớ carry và di chuyển con trỏ l1 sang nút tiếp theo trong danh sách liên kết.

b. Kiểm tra xem l2 có tồn tại hay không. Nếu có, ta cộng giá trị của l2->val với giá trị nhớ carry và di chuyển con trỏ l2 sang nút tiếp theo trong danh sách liên kết.

c. Tạo một nút mới và gán giá trị của carry mod 10 vào nút này (carry % 10). Điều này đảm bảo rằng giá trị trong nút mới sẽ nằm trong khoảng từ 0 đến 9.

d. Chia carry cho 10 để tính toán giá trị nhớ mới để chuyển sang vòng lặp tiếp theo (carry /= 10).

e. Di chuyển con trỏ curr sang nút tiếp theo trong danh sách liên kết.

3. Khi vòng lặp kết thúc, ta trả về nút đầu tiên của danh sách liên kết đã tạo (dummy.next).

Thuật toán này thực hiện phép cộng từng chữ số của hai số theo thứ tự từ phải sang trái. Nếu một trong hai danh sách liên kết có độ dài lớn hơn danh sách còn lại, ta xem như các chữ số còn lại của danh sách dài hơn đều là 0. Giá trị nhớ (carry) được sử dụng để chuyển giá trị lớn hơn 9 sang phần tử tiếp theo của danh sách liên kết. Kết quả là danh sách liên kết chứa tổng của hai số đã cho.

Giải thích thuật toán bằng Java

class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;

    while (l1 != null || l2 != null || carry > 0) {
      if (l1 != null) {
        carry += l1.val;
        l1 = l1.next;
      }
      if (l2 != null) {
        carry += l2.val;
        l2 = l2.next;
      }
      curr.next = new ListNode(carry % 10);
      carry /= 10;
      curr = curr.next;
    }

    return dummy.next;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while carry or l1 or l2:
      if l1:
        carry += l1.val
        l1 = l1.next
      if l2:
        carry += l2.val
        l2 = l2.next
      curr.next = ListNode(carry % 10)
      carry //= 10
      curr = curr.next

    return dummy.next