LeetCode 題庫 - Add Two Numbers (兩數相加)

787 words

4 minutes

LeetCode 題庫 - Add Two Numbers (兩數相加)

2020-12-23

Algorithm

LeetCode

/

C

前言#

是個難度適中的題目。

題目#

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 之外，這兩個數都不會以 0 開頭。

測資#

Example 1：

1
Input: l1 = [2,4,3], l2 = [5,6,4]
2
Output: [7,0,8]
3
Explanation: 342 + 465 = 807.

Example 2：

1
Input: l1 = [0], l2 = [0]
2
Output: [0]

Example 3：

1
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
2
Output: [8,9,9,9,0,0,0,1]

限制#

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

解題思路#

碰壁與問題#

一開始如果你使用將鏈表的單個數字全部轉換成一個完整數字，然後進行相加，在轉換成一個鏈表，這樣會造成 Int 溢出，因為他的節點範圍是 1 ~ 100，所以不能用這個方法。
如果你是要新建第三個的鏈表存結果，然後再將兩者的相加一位一位存到新的鏈表，這樣會很費運行內存，然後考慮的情況變多。
在 C 中我們無法提前知道鏈表的長度。
必須將時間複雜度控制在 O(N)。

解決#

將兩個鏈表上一位一位的相加結果都存到第一個鏈表上，這樣子解決了時間與運行記憶體問題，連帶將需要考慮的情也減少，這樣我們只需要考慮到第一個鏈表的長度不夠，還有相加進位，鏈表的頭節點不為空。

源碼#

我使用 C 語言解決了這題。

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     struct ListNode *next;
6
 * };
7
 */
8

9

10
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
11
    struct ListNode *p = l1, *q = l2;
12

13
    int temp = 0; // 進位相加值
14
    //  b 加到 a 上
15
    while(p || q)
16
    {
17
        if (p && q)
18
        {
19
            // p q 都還沒到尾
20
            temp += p->val + q->val;
21
            q = q->next;
22
        }
23
        else if (p && !q)
24
        {
25
            // q 已經到尾
26
            temp += p->val;
27
        }
28
        else if (!p && q)
29
        {
30
            // p 已經到尾
31
            temp += q->val;
32
            q = q->next;
33
        }
34
        // 將結果寫入
35
        p->val = temp % 10;
36
        temp -= p->val;
37
        temp /= 10;
38
        // 如果還有進位值但 p 已經到尾的情況
39
        // 如果p 已經到尾部 但是 q 還沒到尾部的情況
40
        if (!p->next && (temp != 0 || q))
41
        {
42
            struct ListNode *s = (struct ListNode *)malloc(sizeof(struct ListNode));
43
            s->val = 0;
44
            s->next = NULL;
45
            p->next = s;
46
            //printf("temp %d ,p %d\n", temp, p != NULL);
47
        }
48
        p = p->next;
49
    }
50
    return l1;
51
}