0445 solved.

liuyubobobo · liuyubobobo · commit cc99530d3cf0 · 2019-09-21T23:57:02.000-07:00
diff --git a/0445-Add-Two-Numbers-II/cpp-0445/CMakeLists.txt b/0445-Add-Two-Numbers-II/cpp-0445/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.14)
+project(cpp_0445)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0445 main3.cpp)
diff --git a/0445-Add-Two-Numbers-II/cpp-0445/main.cpp b/0445-Add-Two-Numbers-II/cpp-0445/main.cpp
@@ -0,0 +1,58 @@
+/// Source : https://leetcode.com/problems/add-two-numbers-ii/
+/// Author : liuyubobobo
+/// Time   : 2019-09-21
+
+#include <iostream>
+
+using namespace std;
+
+
+/// Using reverse
+/// Time Complexity: O(m + n + max(m, n))
+/// Space Complexity: O(1)
+
+/// Definition for singly-linked list.
+struct ListNode {
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+class Solution {
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        l1 = reverse(l1);
+        l2 = reverse(l2);
+        ListNode* dummyHead = new ListNode(-1), *cur = dummyHead;
+        int carry = 0;
+        for(ListNode* node1 = l1, *node2 = l2; node1 || node2 || carry;
+            node1 = node1 ? node1->next : NULL, node2 = node2 ? node2->next : NULL){
+
+            int x = node1 ? node1->val : 0;
+            x += node2 ? node2->val : 0;
+            x += carry;
+            cur->next = new ListNode(x % 10);
+            cur = cur->next;
+            carry = x / 10;
+        }
+        return reverse(dummyHead->next);
+    }
+
+private:
+    ListNode* reverse(ListNode* node){
+
+        if(!node->next) return node;
+
+        ListNode* ret = reverse(node->next);
+        node->next->next = node;
+        node->next = NULL;
+        return ret;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/0445-Add-Two-Numbers-II/cpp-0445/main2.cpp b/0445-Add-Two-Numbers-II/cpp-0445/main2.cpp
@@ -0,0 +1,56 @@
+/// Source : https://leetcode.com/problems/add-two-numbers-ii/
+/// Author : liuyubobobo
+/// Time   : 2019-09-21
+
+#include <iostream>
+#include <stack>
+
+using namespace std;
+
+
+/// Using Stack
+/// Time Complexity: O(m + n + max(m, n))
+/// Space Complexity: O(m + n)
+
+/// Definition for singly-linked list.
+struct ListNode {
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+class Solution {
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        stack<ListNode*> stack1, stack2, stack;
+        ListNode* node = l1;
+        while(node) stack1.push(node), node = node->next;
+        node = l2;
+        while(node) stack2.push(node), node = node->next;
+
+        int carry = 0;
+        while(!stack1.empty() || !stack2.empty() || carry){
+
+            int x = 0;
+            if(!stack1.empty()) x += stack1.top()->val, stack1.pop();
+            if(!stack2.empty()) x += stack2.top()->val, stack2.pop();
+            x += carry;
+
+            stack.push(new ListNode(x % 10));
+            carry = x / 10;
+        }
+
+        ListNode* ret = stack.top(), *cur = ret;
+        stack.pop();
+        while(!stack.empty())
+            cur->next = stack.top(), cur = cur->next, stack.pop();
+        return ret;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/0445-Add-Two-Numbers-II/cpp-0445/main3.cpp b/0445-Add-Two-Numbers-II/cpp-0445/main3.cpp
@@ -0,0 +1,79 @@
+/// Source : https://leetcode.com/problems/add-two-numbers-ii/
+/// Author : liuyubobobo
+/// Time   : 2019-09-21
+
+#include <iostream>
+#include <stack>
+
+using namespace std;
+
+
+/// Recursion
+/// Time Complexity: O(m + n + max(m, n))
+/// Space Complexity: O(max(m, n))
+
+/// Definition for singly-linked list.
+struct ListNode {
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+class Solution {
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        int len1 = get_length(l1), len2 = get_length(l2);
+        int len = max(len1, len2);
+
+        if(len1 != len2){
+            ListNode* head = len1 < len2 ? l1 : l2;
+            for(int i = 0; i < len - min(len1, len2); i ++){
+                ListNode* node = new ListNode(0);
+                node->next = head;
+                head = node;
+            }
+            if(len1 < len2) l1 = head;
+            else l2 = head;
+        }
+
+        int carry = 0;
+        ListNode* res = go(l1, l2, carry);
+        if(carry){
+            ListNode* node = new ListNode(1);
+            node->next = res;
+            res = node;
+        }
+        return res;
+    }
+
+private:
+    int get_length(ListNode* head){
+
+        if(!head) return 0;
+        return 1 + get_length(head->next);
+    }
+
+    ListNode* go(ListNode* l1, ListNode* l2, int& carry){
+
+        if(!l1){
+            assert(!l2);
+            carry = 0;
+            return NULL;
+        }
+
+        int c = 0;
+        ListNode* next = go(l1->next, l2->next, c);
+        int x = l1->val + l2->val + c;
+        ListNode* res = new ListNode(x % 10);
+        res->next = next;
+        carry = x / 10;
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -368,6 +368,8 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 443 | [String Compression](https://leetcode.com/problems/string-compression/description/) | | [C++](0443-String-Compression/cpp-0443/) | | |
 | | | | | | |
+| 445 | [Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/) | [无] | [C++](0445-Add-Two-Numbers-II/cpp-0445/) | | |
+| | | | | | |
 | 447 | [Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/description/) | [无] | [C++](0447-Number-of-Boomerangs/cpp-0447/) | [Java](0447-Number-of-Boomerangs/java-0447/src/) | |
 | | | | | | |
 | 450 | [Delete Node in a BST](https://leetcode.com/problems/delete-node-in-a-bst/) | [solution](https://leetcode.com/problems/delete-node-in-a-bst/solution/) | [C++](0450-Delete-Node-in-a-BST/cpp-0450/) | | |
