[LeetCode] Add Two Numbers II 两个数字相加之二

You are given two linked lists representing two non-negative numbers. The most significant digit comes first 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.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

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

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int sum = 0;
ListNode *res = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) {sum += s1.top(); s1.pop();}
if (!s2.empty()) {sum += s2.top(); s2.pop();}
res->val = sum % 10;
ListNode *head = new ListNode(sum / 10);
sum /= 10;
}
return res->val == 0 ? res->next : res;
}
};

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int n1 = getLength(l1), n2 = getLength(l2);
head->next = (n1 > n2) ? helper(l1, l2, n1 - n2) : helper(l2, l1, n2 - n1);
}
}
int cnt = 0;
++cnt;
}
return cnt;
}
ListNode* helper(ListNode* l1, ListNode* l2, int diff) {
if (!l1) return NULL;
ListNode *res = (diff == 0) ? new ListNode(l1->val + l2->val) : new ListNode(l1->val);
ListNode *post = (diff == 0) ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, diff - 1);
if (post && post->val > 9) {
post->val %= 10;
++res->val;
}
res->next = post;
return res;
}
};

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int n1 = getLength(l1), n2 = getLength(l2), diff = abs(n1 - n2);
if (n1 < n2) swap(l1, l2);
ListNode *dummy = new ListNode(0), *cur = dummy, *right = cur;
while (diff > 0) {
cur->next = new ListNode(l1->val);
if (l1->val != 9) right = cur->next;
cur = cur->next;
l1 = l1->next;
--diff;
}
while (l1) {
int val = l1->val + l2->val;
if (val > 9) {
val %= 10;
++right->val;
while (right->next) {
right->next->val = 0;
right = right->next;
}
right = cur;
}
cur->next = new ListNode(val);
if (val != 9) right = cur->next;
cur = cur->next;
l1 = l1->next;
l2 = l2->next;
}
return (dummy->val == 1) ? dummy : dummy->next;
}
int cnt = 0;
++cnt;
}
return cnt;
}
};

|
10月前
|

LeetCode刷题---Two Sum（一）
LeetCode刷题---Two Sum（一）
|
8月前
Leetcode 4. Median of Two Sorted Arrays

19 0
|
8月前
Leetcode 623. Add One Row to Tree

32 0
|
10月前
|

|

LeetCode - #2 Add Two Numbers

62 0
|

LeetCode - #1 Two Sum

46 0
LeetCode 167 Two Sum II - Input array is sorted（输入已排序数组，求其中两个数的和等于给定的数）

70 0
|

LeetCode只出现一次的数字使用JavaScript解题|前端学算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
120 0
|
Python
LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists
LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists
80 0
|

122 0