aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--leetcode/solutions.org83
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