解題說明
Add Two Numbers II
題目描述：給定兩個非空的 linked list，分別代表兩個非負整數。數字以最高位在前（most significant digit first）的方式儲存，每個節點存一位數字。請將兩個數字相加，並以 linked list 的形式回傳結果。注意：這與第 #2 題（Add Two Numbers）的差異在於，#2 是最低位在前，而本題是最高位在前，無法直接從頭節點開始進行進位運算。
解題思路：由於 linked list 只能從頭往尾走，而加法需要從最低位（尾部）開始，因此核心挑戰在於如何取得從尾到頭的順序。
最直觀的方法是使用 stack：分別把兩個 linked list 的所有節點值依序壓入兩個 stack，再依序 pop 出來，此時取出的順序即為從最低位到最高位。每次 pop 出一對數字後，加上進位值 carry，計算出當前位的數值與新的進位。建立新節點後，以「頭插法（prepend）」的方式將其串接到結果 linked list 的最前端，如此最終串出的 list 順序即為由高位到低位。迴圈結束後，若 carry 仍為 1，則需在最前面額外插入一個值為 1 的節點。
此方法不需要修改原始輸入的 linked list，空間複雜度為 O(m + n)。
C++ 解法
複雜度分析
時間複雜度：O(m + n) — 需要各遍歷一次長度為 m 和 n 的兩個 linked list 以建立 stack，再以最多 max(m, n) + 1 次迴圈完成加法，整體為線性時間。
空間複雜度：O(m + n) — 兩個 stack 分別儲存 m 和 n 個節點值，結果 linked list 本身也佔用 O(max(m, n)) 的空間，合計為 O(m + n)。
虛擬碼
1. Create stack s1 and push all values from l1 (head to tail). 2. Create stack s2 and push all values from l2 (head to tail). 3. Initialize carry = 0, result head = null. 4. While s1 is not empty OR s2 is not empty OR carry != 0: a. sum = carry b. If s1 not empty: sum += s1.top(); s1.pop() c. If s2 not empty: sum += s2.top(); s2.pop() d. carry = sum / 10; digit = sum % 10 e. Create new node with value digit. f. Set new node's next = current head. g. Update head = new node (prepend). 5. Return head.
其他解法
方法一：反轉串列後相加
先分別反轉兩個 linked list，使最低位變成頭節點，之後就能像第 #2 題一樣從頭開始逐位相加，最後再將結果串列反轉回來。此方法會直接修改輸入串列（或需要複製），而 stack 方法則不修改原始輸入。時間複雜度同為 O(m + n)，但需要三次遍歷（反轉 l1、反轉 l2、反轉結果），常數因子稍大。
方法二：遞迴法
先計算兩個串列的長度差，將較短的串列以遞迴補零對齊，再從最低位開始回傳進位值。遞迴呼叫的 call stack 扮演了顯式 stack 的角色，因此概念上與 stack 方法相似。此方法的程式碼較為精簡，但遞迴深度為 max(m, n)，在極長串列上可能造成 stack overflow，且可讀性相對較低。
延伸思考
- 如果不允許使用額外的資料結構（例如 stack 或陣列），只能使用 O(1) 的額外空間，你該如何解決本題？（提示：反轉串列本身不需要額外空間）
- 本題要求不修改輸入串列的情況下，stack 方法是最簡潔的選擇。若輸入串列可以被修改，反轉法是否更有優勢？請比較兩者的 trade-off。
- 若數字可以包含前導零（例如
0 -> 0 -> 7代表 7），你需要對程式碼做哪些調整來正確處理輸出中的前導零問題？