Leetcode No.2(Add Two Numbers) 心得(Medium)

ChingYuanYang
Aug 29, 2017 · 2 min read

題目:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

想法:
這題很簡單,可能只是在練習 linked list的解法,還有要考慮進位的情形和兩個 list 可能不同長度。

值得一提的是為了如果要讓 code 更簡潔,網路上用一個 Dummy node,這樣就不用為了第一個 node 再額外處理 (因為第一個 node 是直接 new 給 pointer,第二個以後是要 new 給 node->next)。我的解答沒有這樣做。

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *Head = NULL;
int lr1;
int lr2;
int value;
int leading;

lr1 = l1->val;
lr2 = l2->val;

value = lr1 + lr2;

if (value > 9) {
leading = 1;
value = value — 10;
} else
leading = 0;

ListNode *result = new ListNode(value);
Head = result;

while (l1->next != NULL || l2->next != NULL) {
if (l1->next != NULL) {
l1 = l1->next;
lr1 = l1->val;
}
else
lr1 = 0;
if (l2->next != NULL) {
l2 = l2->next;
lr2 = l2->val;
}
else
lr2 = 0;
value = lr1 + lr2 + leading;
if (value > 9) {
leading = 1;
value = value — 10;
} else
leading = 0;

ListNode *node = new ListNode(value);
result->next = node;
result = result->next;
}

if (leading)
result->next = new ListNode(leading);

return Head;
}
};

網路上解答:
就是剛提到用 dummy node 方式。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade