diff options
Diffstat (limited to 'leetcode')
-rw-r--r-- | leetcode/solutions.org | 83 |
1 files changed, 82 insertions, 1 deletions
diff --git a/leetcode/solutions.org b/leetcode/solutions.org index b8748ce..d78f875 100644 --- a/leetcode/solutions.org +++ b/leetcode/solutions.org @@ -16,7 +16,7 @@ bool containsDuplicate(vector<int> &nums) { std::sort(nums.begin(), nums.end()); const size_t n = nums.size() - 1; - for (const size_t i = 0; i < n; ++i) + for (const size_t i = 0; i < n - 1; ++i) if (nums[i] == nums[i + 1]) return true; return false; @@ -590,4 +590,85 @@ vector<int> dailyTemperatures(vector<int> &temperatures) return days; } #+end_src +* Linked Lists +** TODO (#2) Add two numbers +Given two linked lists representing the digits of a number in reverse +order, return their sum. +#+begin_src c++ :tangle 2.cpp :comments link +#include <bits/stdc++.h> +using namespace std; + +struct ListNode +{ + int val; + ListNode *next; + + ListNode() : val{0}, next{nullptr} + { + } + + ListNode(int val) : val{val}, next{nullptr} + { + } + + ListNode(int val, ListNode *next) : val{val}, next{next} + { + } + + ~ListNode() + { + if (next) + delete next; + } +}; + +ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) +{ + if (!(l1 && l2) || + (l1->val == l2->val && l1->val == 0 && !(l1->next || l2->next))) + return l1; + + int carry = 0; + int sum = l1->val + l2->val; + + ListNode *root = new ListNode(sum % 10); + ListNode *end = root; + + carry = sum / 10; + l1 = l1->next; + l2 = l2->next; + + for (; l1 && l2; l1 = l1->next, l2 = l2->next) + { + sum = l1->val + l2->val + carry; + carry = sum / 10; + sum %= 10; + + auto node = new ListNode(sum, nullptr); + end->next = node; + end = node; + } + + if (l1 || l2) + { + auto remaining = l1 ? l1 : l2; + for (; remaining; remaining = remaining->next) + { + remaining->val += carry; + carry = remaining->val / 10; + remaining->val %= 10; + end->next = remaining; + end = remaining; + } + } + + if (carry != 0) + { + auto node = new ListNode(carry, nullptr); + end->next = node; + } + + return root; +} +#+end_src * Blind 75 |