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++ 在刷題。