โปรแกรมหาตัวเลขที่แทนด้วย Linked List ใน Python

ปัญหา

กำหนด singly linked list สองตัว L1 และ L2 แต่ละตัวแทนตัวเลข โดยตัวเลขหลักหน่วยอยู่ก่อน (least significant digit first) ต้องการหา linked list ของผลบวก

ตัวอย่าง: L1 = [5,6,4] (แทน 465), L2 = [2,4,8] (แทน 842) → ผลบวก 1307 → linked list [7,0,3,1]

อัลกอริทึม

1. carry = 0
2. สร้าง dummy head res = ListNode(0), curr = res
3. วนลูปพร้อม L1 หรือ L2 หรือ carry ไม่เป็นศูนย์:
   • ดึงค่า val จาก L1/L2 (ถ้าเป็น None ให้เป็น 0)
   • sum_ = l0_val + l1_val
   • carry, add_val = divmod(sum_ + carry, 10)
   • สร้าง node ใหม่ค่า add_val ต่อที่ curr.next
   • ขยับ curr, L1, L2
4. ตั้ง curr.next = None
5. คืนค่า res.next (ข้าม dummy head)

การนำไปใช้ 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 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

# Test
ob = Solution()
L1 = make_list([5,6,4])
L2 = make_list([2,4,8])
print_list(ob.solve(L1, L2))

ผลลัพธ์

[7, 0, 3, 1, ]

ตรงกับค่าที่คาดหวัง: 465 + 842 = 1307 → linked list [7,0,3,1] (หลักหน่วยก่อน)