/*
 * 演算法 / Algorithm:
 * 與 C 版相同：從個位開始逐位相加並維護 carry，直到兩串列與進位都用完。
 * Same as the C version: add digit-by-digit from the ones place, maintaining
 * a carry, until both lists and the carry are exhausted. A dummy head node
 * removes the special case for appending the first node.
 */

// LeetCode 已定義 / Provided by LeetCode:
// struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 虛擬頭節點，new 在堆積(heap)上建立一個節點 / dummy head created on the heap
        ListNode* dummy = new ListNode(0);
        // tail 指向結果串列最後一個節點，起點就是 dummy / tail tracks the last result node
        ListNode* tail = dummy;

        int carry = 0;              // 進位 / carry

        // 任一串列還有節點，或還有進位，就繼續 / loop while lists or carry remain
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            // 三元運算子：串列走到底就用 0 / ternary: use 0 when a list is exhausted
            int x = (l1 != nullptr) ? l1->val : 0;
            int y = (l2 != nullptr) ? l2->val : 0;

            int sum = x + y + carry; // 本位總和 / column total
            carry = sum / 10;        // 新進位 / new carry
            // emplace 一個新節點；此處直接 new 建立，值為本位數字 sum % 10
            // create a new node holding this position's digit
            tail->next = new ListNode(sum % 10);
            tail = tail->next;       // tail 前進 / advance tail

            // auto 這裡不需要，直接前進指標 / advance each list pointer if present
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }

        ListNode* head = dummy->next; // 真正答案的開頭 / the real head
        delete dummy;                 // 釋放虛擬頭，避免記憶體洩漏 / free the dummy node
        return head;
    }
};