Giả sử chúng ta có hai linked list không rỗng. Hai list này biểu diễn hai số nguyên không âm. Các chữ số được lưu theo thứ tự ngược. Mỗi node chỉ chứa một chữ số. Cộng hai số và trả về kết quả dưới dạng linked list. Giả định hai số không chứa số 0 dẫn đầu, trừ số 0 chính nó. Ví dụ: 120 + 230, linked list sẽ là [0 → 2 → 1] + [0 → 3 → 2] = [0 → 5 → 3] = 350.
Để giải quyết, chúng ta làm theo các bước:
- Nhận hai list l1 và l2. Khởi tạo head và temp là null
- c := 0 (carry)
- while l1 và l2 đều không rỗng
- nếu l1 không rỗng, a := l1.val, ngược lại a := 0
- nếu l2 không rỗng, b := l2.val, ngược lại b := 0
- n := a + b + c
- nếu n > 9, c := 1 ngược lại 0
- node := tạo node mới với giá trị n % 10
- nếu head là null
- head := node và temp := node
- ngược lại
- head.next := node, và head := node
- l1 := node tiếp theo của l1, nếu l1 tồn tại
- l2 := node tiếp theo của l2, nếu l2 tồn tại
- nếu c khác 0, thì
- node := node mới giá trị 1, next của head := node
- trả về temp
Ví dụ (Python)
Hãy xem triển khai sau để hiểu rõ hơn:
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 addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
head = None
temp = None
c = 0
while l1 or l2:
if not l1:
a = 0
else:
a = l1.val
if not l2:
b = 0
else:
b = l2.val
n = a + b + c
c = 1 if n > 9 else 0
node = ListNode(n % 10)
if not head:
head = node
temp = node
else:
head.next = node
head = node
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
if c:
node = ListNode(1)
head.next = node
return temp
ob1 = Solution()
l1 = make_list([0,2,1])
l2 = make_list([0,3,2])
print_list(ob1.addTwoNumbers(l1, l2))
Input
[0,2,1] [0,3,2]
Output
[0,5,3]