Giả sử chúng ta có hai danh sách liên kết đơn lẻ L1 và L2, mỗi danh sách đại diện cho một số có ít chữ số có nghĩa nhất trước tiên, chúng ta phải tìm danh sách liên kết tổng hợp.
Vì vậy, nếu đầu vào giống như L1 =[5,6,4] L2 =[2,4,8], thì đầu ra sẽ là [7, 0, 3, 1,]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
mang:=0
-
res:=một nút mới có giá trị 0
-
curr:=res
-
trong khi L1 không rỗng hoặc L2 không rỗng hoặc carry khác 0, thực hiện
-
l0_val:=giá trị của L1 nếu L1 không trống, ngược lại là 0
-
l1_val:=giá trị của L2 nếu L2 không trống, ngược lại là 0
-
sum_:=l0_val + l1_val
-
carry:=thương số của (sum_ + carry) / 10
-
add_val:=phần còn lại của (sum_ + carry) / 10
-
curr.next:=một nút mới có giá trị add_val
-
curr:=next of curr
-
L1:=tiếp theo của L1 nếu L1 không trống, ngược lại là rỗng
-
L2:=next of L2 nếu L2 không trống, ngược lại là null
-
-
tiếp theo của curr:=null
-
trở lại tiếp theo của res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
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, ]