/*
 * 演算法 / Algorithm:
 * 從兩串列的頭（個位）同步往後走，逐位相加並維護進位 carry。
 * Walk both lists from the head (ones digit), add digit-by-digit while
 * carrying. Loop while either list has nodes OR carry is nonzero.
 * 用 dummy 虛擬頭節點簡化「接第一個節點」的邏輯。
 */

// LeetCode 已幫我們定義好 ListNode，這裡列出以供參考 / Provided by LeetCode:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    // dummy 是虛擬頭節點，val 隨便給，重點是它的 next 會指向真正答案的第一個節點
    // dummy is a placeholder head; we only care about dummy.next at the end
    struct ListNode dummy;
    dummy.next = NULL;              // 先清空，避免指向垃圾位址 / init to NULL, avoid garbage

    // tail 一直指著「結果串列目前的最後一個節點」，新節點都接在它後面
    // tail always points at the last node of the result; we append after it
    struct ListNode* tail = &dummy; // &dummy 取 dummy 的位址 / take address of dummy

    int carry = 0;                  // 進位，初始沒有進位 / carry, starts at 0

    // 只要還有數字要加（任一串列非空），或還有進位沒處理完，就繼續
    // Continue while either list has nodes, or a carry remains
    while (l1 != NULL || l2 != NULL || carry != 0) {
        // 若 l1 走到底就當作 0，否則取它的值 / use l1's digit, or 0 if exhausted
        int x = (l1 != NULL) ? l1->val : 0;
        // 若 l2 走到底就當作 0，否則取它的值 / use l2's digit, or 0 if exhausted
        int y = (l2 != NULL) ? l2->val : 0;

        int sum = x + y + carry;    // 本位總和 = 兩位數字 + 進位 / column total
        carry = sum / 10;           // 整數除法取進位（0 或 1） / new carry (0 or 1)
        int digit = sum % 10;       // 取餘數得到本位要寫的數字 / digit for this position

        // malloc 向系統要一塊記憶體放新節點，sizeof 算出一個節點多大
        // allocate memory for one new node
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = digit;          // 存入本位數字 / store the digit
        node->next = NULL;          // 目前是最後一個，next 先設 NULL / it's the new tail

        tail->next = node;          // 把新節點接到結果串列尾巴 / append to result
        tail = node;                // tail 前進到這個新節點 / move tail forward

        // 兩個串列各自往後走一格（若還沒到底）/ advance each list if not exhausted
        if (l1 != NULL) l1 = l1->next;
        if (l2 != NULL) l2 = l2->next;
    }

    // 真正的答案從 dummy.next 開始（跳過虛擬頭）/ real answer starts after dummy
    return dummy.next;
}