Try   HackMD

2. Add Two Numbers


My Solution

The Key Idea for Solving This Coding Question

C++ Code

/** * 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) { ListNode *dummy = new ListNode(), *curr = dummy; int carry = 0; while (l1 != nullptr || l2 != nullptr) { int sum = carry; if (l1 != nullptr) { sum += l1->val; l1 = l1->next; } if (l2 != nullptr) { sum += l2->val; l2 = l2->next; } carry = sum /10; sum %= 10; curr->next = new ListNode(sum); curr = curr->next; } if (carry != 0) { curr->next = new ListNode(1); } curr = dummy->next; delete dummy; return curr; } };

Time Complexity

O(max(m,n))
m
l1
的長度
n
l2
的長度

Space Complexity

O(max(m,n))

Miscellaneous

(變形題) 67. Add Binary
class Solution { public: string addBinary(string a, string b) { int i = a.size() - 1, j = b.size() - 1; int carry = 0; string answer; while (i >= 0 || j >= 0) { int sum = carry; if (i >= 0) { sum = sum + (a[i] - '0'); --i; } if (j >= 0) { sum = sum + (b[j] - '0'); --j; } carry = sum / 2; sum %= 2; answer.push_back(sum + '0'); } if (carry != 0) { answer.push_back(carry + '0'); } int left = 0, right = answer.size() - 1; while (left < right) { swap(answer[left++], answer[right--]); } return answer; } };