# 解題紀錄 LeetCode 2

## 題目：將兩個數字相加（Add Two Numbers）

## 📙 題目描述

給定兩個 **non-empty** ``Linked list``
將每個節點相加，如有進位則加到下一個節點。回傳串列的指標

**範例1：**

輸入： l1 = [2,4,3], l2 = [5,6,4]
輸出： [7,0,8]
解釋： 342 + 465 = 807。

**範例2：**

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

---

## ✒️ 解題思路

1. **迴圈遍歷**
- 變數``sum``儲存**兩個節點總和**
- 變數``carry`` 儲存**進位**
2. **迴圈執行條件**
- 當``carry``不為``0``或串列指標不等於``NULL``

---

## 💻 C 語言解法

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode head ;
    struct ListNode* ptr = &head;//用來移動的指標
    int carry = 0;
    while(carry || l1 || l2){
        int sum = carry; //將sum 賦值前一個進位
        if(l1 != NULL){
            sum += l1->val;
            l1 = l1->next;
        }
        if(l2 != NULL){
            sum += l2->val;
            l2 = l2->next;
        }
        carry = sum / 10;
        struct ListNode* new =  malloc(sizeof(struct ListNode)); //串建新節點
        new->val = sum % 10;
        new->next = NULL;
        ptr->next = new;
        ptr = new;
    }
    return head.next;//回傳第一個節點 
}

---

## 🕛時間複雜度分析

- **O(n)**（迴圈遍歷）
- n = **max(len(l1), len(l2))**

---