สมมติว่าเราได้ให้รายการที่เชื่อมโยงที่ไม่ว่างเปล่าสองรายการ สองรายการนี้แสดงตัวเลขจำนวนเต็มไม่เป็นลบสองจำนวน ตัวเลขจะถูกเก็บไว้ในลำดับย้อนกลับ แต่ละโหนดมีตัวเลขเพียงหลักเดียว เพิ่มตัวเลขสองตัวและส่งคืนผลลัพธ์เป็นรายการที่เชื่อมโยง เรากำลังสันนิษฐานว่าตัวเลขทั้งสองไม่มีเลขศูนย์นำหน้า ยกเว้นตัวเลข 0 เอง ดังนั้นหากตัวเลขคือ 120 + 230 รายการที่เชื่อมโยงจะเป็น [0 → 2 → 1] + [0 → 3 → 2] =[0 → 5 → 3] =350
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
- เอาสองรายการ l1 และ l2. เริ่มต้น head และ temp เป็น null
- ค :=0
- ในขณะที่ l1 และ l2 ทั้งคู่เป็นรายการที่ไม่ว่างเปล่า
- หาก l1 ไม่ว่างเปล่า ให้ตั้งค่า a :=0 มิฉะนั้น ให้ตั้งค่า a :=l1.val
- ถ้า l2 ไม่ว่าง ให้ตั้งค่า b :=0 มิฉะนั้น ให้ตั้งค่า b :=l2.val
- n :=a + b + c
- ถ้า n> 9 แล้ว c :=1 มิฉะนั้น 0
- node :=สร้างโหนดใหม่ด้วยค่า n mod 10
- ถ้าหัวเป็นโมฆะ
-
หัว :=โหนดและอุณหภูมิ :=โหนด
-
- อย่างอื่น
- head.next :=โหนด และ head :=โหนด
- l1 :=โหนดถัดไปของ l1 ถ้ามี l1 อยู่
- l2 :=โหนดถัดไปของ l2 ถ้ามี l2 อยู่
- ถ้า c ไม่ใช่ศูนย์ แล้ว
- โหนด :=โหนดใหม่ที่มีค่า 1 ถัดไปของส่วนหัว :=โหนด
- อุณหภูมิกลับ
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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)) อินพุต
[0,2,1] [0,3,2]
ผลลัพธ์
[0,5,3]
