สมมติว่าเรามีรายการที่เชื่อมโยงกันสองรายการ L1 และ L2 ซึ่งแต่ละรายการแสดงตัวเลขที่มีเลขนัยสำคัญน้อยที่สุดก่อน เราต้องหารายการที่เชื่อมโยงแบบรวมเข้าด้วยกัน
ดังนั้น หากอินพุตเป็นเหมือน L1 =[5,6,4] L2 =[2,4,8] เอาต์พุตจะเป็น [7, 0, 3, 1, ]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
พก :=0
-
res :=โหนดใหม่ที่มีค่า 0
-
curr :=res
-
ในขณะที่ L1 ไม่ว่างเปล่า หรือ L2 ไม่ว่างเปล่า หรือการพกพาไม่ใช่ศูนย์ ให้ทำ
-
l0_val :=ค่าของ L1 ถ้า L1 ไม่ว่างเปล่า มิฉะนั้น 0
-
l1_val :=ค่าของ L2 ถ้า L2 ไม่ว่างเปล่า มิฉะนั้น 0
-
sum_ :=l0_val + l1_val
-
carry :=ผลหารของ (sum_ + carry) / 10
-
add_val :=ส่วนที่เหลือของ (sum_ + carry) / 10
-
curr.next :=โหนดใหม่ที่มีค่า add_val
-
curr :=ถัดไปของ curr
-
L1 :=ถัดไปของ L1 ถ้า L1 ไม่ว่างเปล่า มิฉะนั้น null
-
L2 :=ถัดไปของ L2 หาก L2 ไม่ว่างเปล่า มิฉะนั้น จะเป็นโมฆะ
-
-
ถัดไปของสกุลเงิน :=null
-
กลับถัดไปของความละเอียด
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
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)) อินพุต
[5,6,4], [2,4,8]
ผลลัพธ์
[7, 0, 3, 1, ]
