---
title: 'Leetcode 第2題 題解 — C++'
disqus: hackmd
---

# Leetcode 第2題 題解 — C++
:::info
:bulb: 此筆記為Leetcode 第 2 題的題目詳解，包含解題思路、C++範例程式碼。
:::

## 2. [Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)

### 解題思路
:::warning
這題題目主要是考驗鏈結串列（Linked List）。
我先創建一個虛擬的開始節點存放串列 l3（一開始為 0），並建立 temp_l3 作為指針指向串列的結尾節點（一開始會是 0）。
若 l1 或 l2 或 carry(進位) 還有值沒使用就進入 while 迴圈，利用 sum 儲存該位置的加總，並將 sum 除以 10 的餘數設為下一位的 carry，sum 只保留個位（sum = sum 除以 10），再將 sum 存入新節點並把 temp_l3 指向新的節點。
回傳數值的時候將拋棄一開始創建的虛擬節點 0，其餘作為回傳值。
:::

### 範例程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode l3(0);
        ListNode* temp_l3 = &l3;
        int sum = 0, carry = 0;

        while (l1 || l2 || carry) {
            sum = carry;

            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            sum = sum % 10;

            temp_l3->next = new ListNode(sum);
            temp_l3 = temp_l3->next;
        }

        return l3.next;
    }
    
};

### 運行結果
**Time Complexity**: O(n)
**Space Complexity**: O(n)
**Runtime**:
0 ms | Beats 100.00%
**Memory**:
77.08 MB | Beats 76.33%

###### tags: `LeetCode Medium`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::