สมมติว่าเรามี linked list สองตัวที่ไม่ว่างเปล่า สองลิสต์นี้แทนจำนวนเต็มสองจำนวนที่ไม่เป็นลบ ตัวเลขถูกเก็บในลำดับย้อนกลับ แต่ละโนดมีเพียงหนึ่งตัวเลข บวกสองจำนวนและคืนค่าผลลัพธ์เป็น linked list เราสมมติว่าสองจำนวนไม่มี leading zeros ยกเว้นจำนวน 0 เอง ดังนั้นถ้าจำนวนคือ 120 + 230 linked list จะเป็น [0 → 2 → 1] + [0 → 3 → 2] = [0 → 5 → 3] = 350
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- รับสองลิสต์ l1 และ l2 เริ่มต้น head และ temp เป็น null
- c := 0
- while 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 เป็น null
- head := node และ temp := node
- อื่นๆ
- head.next := node และ head := node
- l1 := โนดถัดไปของ l1 ถ้ามี
- l2 := โนดถัดไปของ l2 ถ้ามี
- ถ้า c ไม่เป็นศูนย์ แล้ว
- node := โนดใหม่ค่า 1 next ของ head := node
- คืนค่า temp
ตัวอย่าง (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))Input
[0,2,1] [0,3,2]Output
[0,5,3]