2. Add Two Numbers

Đề bài

Bạn được cho 2 danh sách liên kết (linked list) không rỗng, mỗi danh sách biểu diễn một số nguyên không âm.
Các chữ số được lưu theo thứ tự ngược (chữ số hàng đơn vị ở trước), và mỗi nút (node) chỉ chứa đúng một chữ số.
Hãy cộng hai số đó và trả về kết quả dưới dạng một linked list.

Bạn có thể giả định hai số không có số 0 ở đầu (leading zero), ngoại trừ trường hợp số 0.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Giải thích: 342 + 465 = 807.

Tóm tắt đề

Có 2 linked list lưu chữ số theo thứ tự ngược. Yêu cầu cộng từ hàng thấp lên, và kết quả cũng trả về theo thứ tự ngược. Giá trị trả về là node đầu của linked list kết quả.

Ý tưởng

Điểm cần chú ý nhất là xử lý số nhớ (carry).

Trường hợp “căng” (extreme case), ví dụ:

Input: (9 -> 9 -> 9 -> 9 -> 9) + (1 -> )
Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1

Để xử lý thống nhất, ta tạo một nút giả (dummy head), Next của nó trỏ tới head thật của danh sách kết quả. Nhờ vậy không cần xử lý riêng phần head, cứ chạy vòng lặp là được.
Ngoài ra, điều kiện dừng vòng lặp không nên là p.Next != nil (vì như vậy chữ số cuối lại phải xử lý thêm). Thay vào đó, điều kiện hợp lý là p != nil (hoặc tương đương trong code hiện tại: lặp khi còn l1/l2 hoặc còn carry).

Code

package leetcode

/**
 * Định nghĩa cấu trúc danh sách liên kết đơn.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{Val: 0}
	n1, n2, carry, current := 0, 0, 0, head
	for l1 != nil || l2 != nil || carry != 0 {
		if l1 == nil {
			n1 = 0
		} else {
			n1 = l1.Val
			l1 = l1.Next
		}
		if l2 == nil {
			n2 = 0
		} else {
			n2 = l2.Val
			l2 = l2.Next
		}
		current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
		current = current.Next
		carry = (n1 + n2 + carry) / 10
	}
	return head.Next
}

---