Cho hai danh sách liên kết đơn L1, L2 biểu diễn hai số (chữ số ít nghĩa trước), tìm danh sách liên kết biểu diễn tổng của hai số.
Ví dụ: L1 = [5,6,4] (số 465), L2 = [2,4,8] (số 842) -> Tổng = 1307 -> Kết quả [7,0,3,1].
Giải thuật
- Khởi tạo carry = 0, nút kết quả dummy.
- Duyệt L1, L2 cho đến khi cả hai rỗng và carry=0.
- Lấy giá trị nút hiện tại (0 nếu rỗng).
- Tổng = val1 + val2 + carry.
- carry, digit = divmod(sum, 10).
- Tạo nút mới với digit, nối vào kết quả.
- Di chuyển con trỏ L1, L2, curr.
- Trả về next của dummy.
Ví dụ
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end='')
while ptr:
print(ptr.val, end=', ')
ptr = ptr.next
print(']')
class Solution:
def solve(self, L1, L2):
carry = 0
res = ListNode(0)
curr = res
while L1 or L2 or carry:
l0_val = L1.val if L1 else 0
l1_val = L2.val if L2 else 0
sum_ = l0_val + l1_val
carry, add_val = divmod(sum_ + carry, 10)
curr.next = ListNode(add_val)
curr = curr.next
L1 = L1.next if L1 else None
L2 = L2.next if L2 else None
curr.next = None
return res.next
ob = Solution()
L1 = make_list([5, 6, 4])
L2 = make_list([2, 4, 8])
print_list(ob.solve(L1, L2))
Đầu vào
[5,6,4], [2,4,8]
Đầu ra
[7, 0, 3, 1, ]