Add 002 Code

MisterBooo · MisterBooo · commit 781bbb5797ea · 2018-12-13T09:32:00.000+08:00
diff --git a/0002-Add-Two-Numbers/cpp-0002/CMakeLists.txt b/0002-Add-Two-Numbers/cpp-0002/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(cpp_0002)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main2.cpp)
+add_executable(cpp_0002 ${SOURCE_FILES})
diff --git a/0002-Add-Two-Numbers/cpp-0002/main.cpp b/0002-Add-Two-Numbers/cpp-0002/main.cpp
@@ -0,0 +1,49 @@
+/// Source : https://leetcode.com/problems/add-two-numbers/description/
+/// Author : liuyubobobo
+/// Time   : 2018-08-09
+
+#include <iostream>
+
+using namespace std;
+
+/// Definition for singly-linked list.
+struct ListNode {
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+
+/// 时间复杂度: O(n)
+/// 空间复杂度: O(n)
+class Solution {
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        ListNode *p1 = l1, *p2 = l2;
+        ListNode *dummyHead = new ListNode(-1);
+        ListNode* cur = dummyHead;
+        int carried = 0;
+        while(p1 || p2 ){
+            int a = p1 ? p1->val : 0;
+            int b = p2 ? p2->val : 0;
+            cur->next = new ListNode((a + b + carried) % 10);
+            carried = (a + b + carried) / 10;
+
+            cur = cur->next;
+            p1 = p1 ? p1->next : NULL;
+            p2 = p2 ? p2->next : NULL;
+        }
+
+        cur->next = carried ? new ListNode(1) : NULL;
+        ListNode* ret = dummyHead->next;
+        delete dummyHead;
+        return ret;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/0002-Add-Two-Numbers/cpp-0002/main2.cpp b/0002-Add-Two-Numbers/cpp-0002/main2.cpp
@@ -0,0 +1,54 @@
+/// Source : https://leetcode.com/problems/add-two-numbers/description/
+/// Author : liuyubobobo
+/// Time   : 2018-08-09
+
+#include <iostream>
+
+using namespace std;
+
+/// Definition for singly-linked list.
+struct ListNode {
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+
+/// Using l1 as the result list
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        ListNode *p1 = l1, *p2 = l2;
+        ListNode* pre = NULL;
+        int carried = 0;
+
+        while(p1 || p2){
+            int a = p1 ? p1->val : 0;
+            int b = p2 ? p2->val : 0;
+            if(p1)
+                p1->val = (a + b + carried) % 10;
+            else{
+                pre->next = new ListNode((a + b + carried) % 10);
+                p1 = pre->next;
+            }
+            carried = (a + b + carried) / 10;
+
+            pre = p1;
+            p1 = p1->next;
+            if(p2) p2 = p2->next;
+        }
+
+        pre->next = carried ? new ListNode(1) : NULL;
+        return l1;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/0002-Add-Two-Numbers/cpp-0002/main3.cpp b/0002-Add-Two-Numbers/cpp-0002/main3.cpp
@@ -0,0 +1,59 @@
+/// Source : https://leetcode.com/problems/add-two-numbers/description/
+/// Author : liuyubobobo
+/// Time   : 2018-08-09
+
+#include <iostream>
+
+using namespace std;
+
+/// Definition for singly-linked list.
+struct ListNode {
+    int val;
+    ListNode *next;
+    ListNode(int x) : val(x), next(NULL) {}
+};
+
+
+/// Using the longest list in l1 and l2 as the result list
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+
+public:
+    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+
+        int len1 = getLen(l1), len2 = getLen(l2);
+        ListNode *p1 = len1 > len2 ? l1 : l2;
+        ListNode *p2 = len1 > len2 ? l2 : l1;
+
+        ListNode* pre = NULL;
+        int carried = 0;
+        while(p1){
+            int a = p1->val;
+            int b = p2 ? p2->val : 0;
+            p1->val = (a + b + carried) % 10;
+            carried = (a + b + carried) / 10;
+
+            pre = p1;
+            p1 = p1->next;
+            p2 = p2 ? p2->next : NULL;
+        }
+
+        pre->next = carried ? new ListNode(1) : NULL;
+        return len1 > len2 ? l1 : l2;
+    }
+
+private:
+    int getLen(ListNode* l){
+        int res = 0;
+        while(l)
+            res ++, l = l -> next;
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
