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

2020-12-23 約 396 字預計閱讀 2 分鐘

前言

是個難度適中的題目。

題目

題目描述

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
2
3


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

Example 2：

1
2


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

Example 3：

1
2


Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
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
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *p = l1, *q = l2;
    
    int temp = 0; // 進位相加值
    //  b 加到 a 上
    while(p || q)
    {
        if (p && q)
        {
            // p q 都還沒到尾
            temp += p->val + q->val;
            q = q->next;
        }
        else if (p && !q)
        {
            // q 已經到尾
            temp += p->val;
        }
        else if (!p && q)
        {
            // p 已經到尾
            temp += q->val;
            q = q->next;
        }
        // 將結果寫入
        p->val = temp % 10;
        temp -= p->val;
        temp /= 10;
        // 如果還有進位值但 p 已經到尾的情況
        // 如果p 已經到尾部 但是 q 還沒到尾部的情況
        if (!p->next && (temp != 0 || q))
        {
            struct ListNode *s = (struct ListNode *)malloc(sizeof(struct ListNode));
            s->val = 0;
            s->next = NULL;
            p->next = s;
            //printf("temp %d ,p %d\n", temp, p != NULL);
        }
        p = p->next;
    }
    return l1;
}

結語

解這題的前提是需要理解鏈表的概念，其次我自己在本地寫輸入測資時寫得很麻煩，因為 LeetCode 上的編輯器沒有給 main 函數，也無法 Debug（貌似要充錢）。

目錄

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

前言

題目

題目描述

測資

限制

解題思路

碰壁與問題

解決

源碼

結語