Skip to content

LeetCode: 2-Add Two Numbers 解題紀錄

Last Updated on 2021-05-09 by Clay

題目

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.

Example:

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

在這個題目中，我們會得到兩個以 Linked List 結構儲存的數值，而最終目的就是把這兩個 Linked List 的值相加，並返回相加結果的 Linked List 結構的資料。

解題思路

一開始我嘗試了建立『第三個 Linked List』並把兩個 Linked List 相加，並將相加結果存入第三個 Linked List。乍看之下似乎相當直觀，但實際跑出來的結果顯示我所使用的記憶體較他人來得更多。

想了一陣子，最終我想到了只固定使用其中一個 Linked List 來加上另外一個 Linked List 的數值，並隨時確認進位 —— 這樣一來我就不用再多開第三個 Linked List 了。

這種做法的話，又分成三種情況：

  • L1 先結束：直接將 next 指向 L2 剩下的鏈結，回傳結果
  • L2 先結束：直接回傳 L1 結果
  • L1 和 L2 同時結束：同樣直接回傳 L1 結果

當然，還是要隨時確認進位。

C++ 程式碼

/**
 * 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) {
        // Init
        ListNode *currentNode = new ListNode(0, l1);
        
        
        // Traverse
        while (true) {
            // Sum
            currentNode->next->val += l2->val;
            
            // Carry
            if (currentNode->next->val >= 10) {
                currentNode->next->val %= 10;

                if (currentNode->next->next != NULL) {
                    ++currentNode->next->next->val;
                }
                else {
                    ListNode *newNode = new ListNode(1);
                    currentNode->next->next = newNode;
                    currentNode->next->val %= 10;
                }
            }

            // Check
            if (currentNode->next->next == NULL && l2->next == NULL) {
                break;
            }
            else if (currentNode->next->next != NULL && l2->next == NULL) {
                l2->next = new ListNode(0, NULL);
            }
            else if (currentNode->next->next == NULL && l2->next != NULL) {
                currentNode->next->next = l2->next;
                break;
            }
            
            // Forward
            currentNode->next = currentNode->next->next;
            l2 = l2->next;
        }
        
        return l1;
    }
};




Python 程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        current = ListNode()
        current.next = l1
        
        while True:
            current.next.val += l2.val
            
            # Carry
            if current.next.val >= 10 and current.next.next != None:
                current.next.val -= 10
                current.next.next.val += 1
            elif current.next.val >= 10 and current.next.next == None:
                current.next.val -= 10
                current.next.next = ListNode(1);
            
            # Forward
            if current.next.next != None:
                current.next = current.next.next
            else:
                current.next.next = l2.next;
                current.next = current.next.next
                l2.next = None;
                
            if l2.next != None:
                l2 = l2.next
            else:
                l2.val = 0
            
            if current.next == None and l2.next == None:
                break
        
        return l1


有趣的是，我自認所用的兩種程式語言其解題過程應該是一致的，不過在 C++ 跑分結果卻差不多都是 85% - 95%（執行速度和記憶體使用率），而在 Python 卻只在 50% 上下？

難道 Python 有什麼特殊解題技巧嗎？關於這點我目前沒有去認真研究，畢竟主要還是拿 C++ 在刷題。

References

Tags:

Leave a Reply