前言

嘿嘿～今天我們要來挑戰一道非常有趣的題目——Add Two Numbers（加法運算的鏈結串列表示）！
這題要求我們將兩個用反序鏈結串列表示的非負整數加起來，並將結果以同樣的鏈結串列形式返回。

這聽起來是不是有點像在處理小學的算術題呢？但其實這道題目能夠考驗我們如何處理進位邏輯和操作鏈結串列。那我們就一起來看看解法吧！

英文題目 Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

題目描述：

給定兩個反序鏈結串列，分別代表兩個非負整數，要求將兩個數字相加，並返回其加總結果的鏈結串列形式。
你可以假設這兩個數字沒有任何前導零，除了數字 0 本身。

Example 1:

難度：Medium

範例 1：

輸入： l1 = [2, 4, 3], l2 = [5, 6, 4]

輸出： [7, 0, 8]

解釋： 342 + 465 = 807

範例 2：

輸入： l1 = [0], l2 = [0]

輸出： [0]

範例 3：

輸入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

輸出： [8,9,9,9,0,0,0,1]

實作

我們可以遍歷兩個鏈結串列，從每個節點取出對應的數字進行加法運算，同時處理進位，並將結果存入新的鏈結串列中：

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let dummy = new ListNode(0); // 用來連接結果鏈結串列的虛擬頭節點
    let p = l1, q = l2, current = dummy;
    let carry = 0; // 用來保存進位

    while (p !== null || q !== null) {
        const x = (p !== null) ? p.val : 0;
        const y = (q !== null) ? q.val : 0;
        const sum = carry + x + y;
        
        carry = Math.floor(sum / 10); // 計算進位
        current.next = new ListNode(sum % 10); // 將計算結果的個位數存入當前節點
        current = current.next; // 移動到下一個節點
        
        if (p !== null) p = p.next;
        if (q !== null) q = q.next;
    }

    // 若最後仍有進位，則新增一個節點存儲進位值
    if (carry > 0) {
        current.next = new ListNode(carry);
    }

    return dummy.next; // 返回虛擬頭節點的下一個節點，為實際的加總結果
}

解題心法

1. 逐位相加並處理進位

   我們將兩個鏈結串列的對應節點相加，並處理進位情況。
   每次加法時，我們將兩個數字加上上一輪的進位，並將結果拆分為個位數和進位。例如，7 + 5 = 12，個位數是 2，進位是 1。

2. 處理鏈結串列不同長度的情況

   我們在遍歷時，如果某個鏈結串列的長度比另一個短，則可以用 0 作為該位置的值，這樣就避免了長度不一致帶來的問題。

3. 額外處理最後的進位

   當我們遍歷完所有的節點後，可能還會有剩餘的進位。如果有，我們需要在結果鏈結串列的最後新增一個節點來存儲這個進位。

為什麼這樣處理？

這種處理方式的核心在於保持計算的簡潔性和高效性，使用一個指針同時遍歷兩個鏈結串列，並即時處理進位情況。
這樣的做法不需要事先反轉鏈結串列或使用額外的空間來存儲中間結果，使得解法的時間複雜度為 O(n)，且空間複雜度也保持在 O(n)。

本次要點：

• 使用指針遍歷兩個鏈結串列，逐位相加並處理進位。
• 處理長度不一致的鏈結串列，未對應的節點用 0 填補。
• 若最後仍有進位，則新增一個節點來存儲進位值。

鏈結串列定義補充

鏈結串列（Linked List）是一種線性數據結構，由一組節點（Node）組成，其中每個節點包含兩個部分：

1. 資料部分（Data）：存儲節點的值或數據。
2. 指標部分（Next/Pointer）：指向下一個節點的引用或地址。

鏈結串列的特點：

• 動態大小：與陣列不同，鏈結串列的大小是動態的，可以根據需要增減節點。
• 非連續記憶體分佈：鏈結串列的節點並不必須存儲在連續的記憶體位置，節點之間是通過指標來關聯的。
• 高效插入和刪除操作：插入或刪除節點只需要修改相鄰節點的指標，時間複雜度通常為 O(1)。
• 隨機訪問效率低：與陣列相比，鏈結串列的隨機訪問效率較低，因為必須從頭開始逐一遍歷節點，時間複雜度為 O(n)。

常見的鏈結串列類型：

1. 單向鏈結串列（Singly Linked List）：每個節點只指向下一個節點，沒有指向前一個節點。

   • 節點結構：[Data | Next]

2. 雙向鏈結串列（Doubly Linked List）：每個節點有兩個指標，分別指向前一個節點和下一個節點。

   • 節點結構：[Prev | Data | Next]

3. 環狀鏈結串列（Circular Linked List）：最後一個節點的指標指向第一個節點，形成環狀結構。

單向鏈結串列的節點定義（以剛剛實作為例）

class ListNode {
    val: number;
    next: ListNode | null;
    
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

在這個範例中，每個 ListNode 都包含一個 val（數據值）和一個 next（指向下一個節點的指標）。

解完這道題目，是不是覺得加法運算變得沒那麼可怕了呢？
其實，就像寫程式一樣，人生中遇到的難題，也都是一步步累積出來的，每解決一個問題就離成功更近一點～
希望大家能帶著這份成就感，繼續面對每個挑戰！
加油喔！我們下次再一起突破更多有趣的題目～٩(^ᴗ^)۶💙