LeetCode #2 Add Two Numbers: บวก linked list ด้วย carry ทีละหลัก

Add Two Numbers ให้เลขไม่ติดลบสองจำนวนมาเป็น linked list โดยเก็บหลักหน่วยไว้หน้า เช่น 2 → 4 → 3 แทน 342 แล้วให้คืนผลบวกในรูปเดียวกันครับ จุดสำคัญไม่ใช่แค่บวกได้ แต่ต้องจัดการ carry หรือ “เลขทด” เมื่อ list ยาวไม่เท่ากันและเมื่อหลักสุดท้ายยังมีทดค้าง

วิธี 1: แปลงเป็นจำนวนเต็มแล้วบวก

เดินแต่ละ list เพื่อประกอบจำนวนเต็ม บวก แล้วแตกกลับเป็น list เวลา O(n + m) และต้องเก็บ integer ที่โตตามจำนวนหลัก วิธีนี้อ่านง่ายใน Python เพราะ integer โตได้ตามหน่วยความจำ แต่ไม่ใช่คำตอบที่พกข้ามภาษาได้ดี: Java long ล้นได้เมื่อโจทย์ยาว และวิธีนี้ไม่ฝึก invariant ของ linked list จึงเหมาะเป็น oracle ใน test มากกว่าคำตอบ default

วิธี 2: เดินสอง list พร้อม carry

ใช้ dummy head เป็นหัวชั่วคราว แล้วอ่านค่าจากแต่ละ list ถ้ายังมี node บวกกับ carry เดิม เขียน sum % 10 เป็น node ใหม่ และส่ง sum // 10 ไปหลักถัดไป เหมือนพนักงานคิดเงินรวมเหรียญสองถาดทีละช่อง ถ้าเต็มสิบก็ส่งคูปองทดไปช่องหน้า วิธีนี้เวลา O(max(n,m)), ใช้พื้นที่ผลลัพธ์ O(max(n,m)) และพื้นที่ช่วย O(1) เป็นคำตอบ default ที่ชัดที่สุด

วิธี 3: recursion ตามหลัก

เขียนฟังก์ชันรับ node ซ้าย ขวา และ carry แล้วเรียกตัวเองกับ .next โค้ดสะท้อนนิยามคณิตศาสตร์และไม่ต้องมี dummy head แต่ใช้ call stack O(max(n,m)) จึงเสี่ยง stack overflow เมื่อ input ยาวมาก เวลาเท่ากับวิธี iterative

from __future__ import annotations

import unittest
from dataclasses import dataclass


@dataclass
class ListNode:
    val: int
    next: "ListNode | None" = None


def from_digits(values: list[int]) -> ListNode:
    head = tail = ListNode(values[0])
    for value in values[1:]:
        tail.next = ListNode(value)
        tail = tail.next
    return head


def to_digits(node: ListNode | None) -> list[int]:
    out: list[int] = []
    while node:
        out.append(node.val)
        node = node.next
    return out


def add_iterative(a: ListNode | None, b: ListNode | None) -> ListNode:
    dummy = tail = ListNode(0)
    carry = 0
    while a or b or carry:
        total = carry + (a.val if a else 0) + (b.val if b else 0)
        carry, digit = divmod(total, 10)
        tail.next = ListNode(digit)
        tail = tail.next
        a = a.next if a else None
        b = b.next if b else None
    return dummy.next


def add_recursive(a: ListNode | None, b: ListNode | None, carry: int = 0) -> ListNode | None:
    if not a and not b and not carry:
        return None
    total = carry + (a.val if a else 0) + (b.val if b else 0)
    next_a = a.next if a else None
    next_b = b.next if b else None
    return ListNode(total % 10, add_recursive(next_a, next_b, total // 10))


class AddTwoNumbersTests(unittest.TestCase):
    def test_both_methods_and_carry_edges(self):
        cases = [([2, 4, 3], [5, 6, 4], [7, 0, 8]), ([0], [0], [0]), ([9, 9], [1], [0, 0, 1])]
        for left, right, expected in cases:
            for solve in (add_iterative, add_recursive):
                self.assertEqual(to_digits(solve(from_digits(left), from_digits(right))), expected)


if __name__ == "__main__":
    unittest.main()

ตัวอย่าง Java ใช้ iterative ซึ่งเป็น default และเปิด assertion เป็น test harness จริง

public class Main {
    record Node(int value, Node next) {}

    static Node add(Node a, Node b) {
        Node reversed = null;
        int carry = 0;
        while (a != null || b != null || carry != 0) {
            int total = carry + (a == null ? 0 : a.value()) + (b == null ? 0 : b.value());
            reversed = new Node(total % 10, reversed);
            carry = total / 10;
            a = a == null ? null : a.next();
            b = b == null ? null : b.next();
        }
        Node result = null;
        while (reversed != null) {
            result = new Node(reversed.value(), result);
            reversed = reversed.next();
        }
        return result;
    }

    static Node list(int... digits) {
        Node head = null;
        for (int i = digits.length - 1; i >= 0; i--) head = new Node(digits[i], head);
        return head;
    }

    static String show(Node node) {
        StringBuilder out = new StringBuilder();
        while (node != null) {
            if (!out.isEmpty()) out.append(',');
            out.append(node.value());
            node = node.next();
        }
        return out.toString();
    }

    public static void main(String[] args) {
        assert show(add(list(2, 4, 3), list(5, 6, 4))).equals("7,0,8");
        assert show(add(list(9, 9), list(1))).equals("0,0,1");
        System.out.println("2 assertions passed");
    }
}

Edge cases ที่ต้องลอง

• list สองฝั่งมีหลักเดียวเป็นศูนย์
• ความยาวไม่เท่ากัน เช่น 99 + 1
• หลักสุดท้ายสร้าง node ใหม่จาก carry
• ห้ามสมมติว่า node ที่หายมีค่าอื่นนอกจากศูนย์
• ไม่แก้ node เดิม เว้นแต่ API ระบุชัดว่าอนุญาต mutation

Decision table

เงื่อนไข	แปลงเป็น integer	Iterative carry	Recursive carry
input ใหญ่มาก	เสี่ยงชนขอบภาษา	ดีที่สุด	เสี่ยง stack
extra memory	integer ใหญ่ + ผลลัพธ์	ผลลัพธ์ + O(1)	ผลลัพธ์ + stack
readability	สั้นแต่ซ่อนข้อจำกัด	ชัดและพกข้ามภาษา	นิยามสวย
sorted input	ไม่เกี่ยว	ไม่เกี่ยว	ไม่เกี่ยว
streaming	ต้องเห็นครบเพื่อประกอบ integer	ประมวลผลทีละ node ได้	ต้องรักษา stack
mutation input	ไม่จำเป็น	ไม่จำเป็น	ไม่จำเป็น

ผมเลือก iterative carry เป็น default เพราะตรง constraints, ไม่ผูกกับ big integer และอธิบาย invariant ได้ง่าย: ก่อนเริ่มรอบใหม่ carry คือค่าที่ต้องส่งจากหลักก่อนหน้าเท่านั้น

Recap

• เดินจนกว่า list ทั้งคู่และ carry จะหมด
• ใช้ divmod หรือ % 10 กับ // 10 แยกหลักและเลขทด
• เทสต์ list ยาวไม่เท่ากันและ carry ทะลุหลักสุดท้าย
• ระบุชัดว่าคำตอบสร้าง list ใหม่ ไม่ mutate input