445. Add Two Numbers II (Medium)

Q:

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

 

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

Follow up: Could you solve it without reversing the input lists?

A:

用vector保存，方便取最后一位

/**

* 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) {

vector<int> V1, V2;

while (l1) {

V1.push_back(l1->val);

l1 = l1->next;

}

while (l2) {

V2.push_back(l2->val);

l2 = l2->next;

}

ListNode header;

int carry = 0;

while (!(V1.empty() && V2.empty()) || carry) {

int a = 0, b = 0;

if (!V1.empty()) {

a = V1.back();

V1.pop_back();

}

if (!V2.empty()) {

b = V2.back();

V2.pop_back();

}

int sum = a + b + carry;

ListNode* tmp = new ListNode(sum % 10, header.next);

header.next = tmp;

carry = sum / 10;

}

return header.next;

}

};

Errors:

1: ListNode* tmp = new ListNode(sum % 10, header.next);

new的结果必须是 指针

2:   need also check       carry != 0