题目描述
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.
Example1:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
解题思路
- 链表的相加
- 按照规则，一步一步来就可
- 这里l1和l2的长度不一定向相等，所以循环的时候，循环条件应该是或的存在
- 记住有一个进位的问题，所以最后一次迭代也可能是只有一个carry
- 这里定义一个新链表的head，一个迭代器，如果是第一次相加，就初始化头节点和迭代器指针
- 不是第一次相加的话，就移动迭代指针即可。
- 可以生成一个假的头节点，这样就不需要单独处理头节点了
/**
* 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) {
if(l1 == nullptr && l2 == nullptr){
return nullptr;
}
if(l1 == nullptr){
return l2;
}
if(l2 == nullptr){
return l1;
}
ListNode* dummyHead = new ListNode(0);
ListNode* dummyNode = dummyHead;
int carry = 0;
while(l1 || l2 || carry){
ListNode* temp = new ListNode(0);
if(l1){
temp -> val += l1 -> val;
l1 = l1 -> next;
}
if(l2){
temp -> val += l2 -> val;
l2 = l2 -> next;
}
if(carry){
temp -> val += carry;
carry = 0;
}
if(temp -> val >= 10){
carry = temp -> val / 10;
temp -> val %= 10;
}
dummyNode -> next = temp;
dummyNode = temp;
}
return dummyHead -> next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
ListNode* pNode;
ListNode* preNode = new ListNode(-1);
ListNode* pHead = preNode;
while(l1 || l2 || carry){
pNode = new ListNode(0);
if(l1){
pNode -> val += l1 -> val;
l1 = l1 -> next;
}
if(l2){
pNode -> val += l2 -> val;
l2 = l2 -> next;
}
if(carry){
pNode -> val += carry;
}
carry = pNode -> val / 10;
pNode -> val = (pNode -> val) % 10;
preNode -> next = pNode;
preNode = pNode;
}
return pHead -> next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1 == NULL && l2 == NULL){
return NULL;
}
ListNode* head = NULL;
ListNode* pNode = NULL;
int carry = 0;
while(l1 || l2 || carry){
int data = 0;
if(l1){
data += l1 -> val;
l1 = l1 -> next;
}
if(l2){
data += l2 -> val;
l2 = l2 -> next;
}
data += carry;
carry = data >= 10 ? data / 10 : 0;
ListNode* newNode = new ListNode(data % 10);
if(!pNode){ // 如果是第一次相加，PNode还没有初始化，那么需要给头结点，指向头结点的指针赋值
head = newNode;
pNode = newNode;
}else{
pNode -> next = newNode; // 移动指针即可
pNode = newNode;
}
}
return head;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1 == nullptr && l2 == nullptr){
return nullptr;
}
if(!l1 && l2){
return l2;
}
if(l1 && !l2){
return l1;
}
int carry = 0;
ListNode* copyNode = nullptr;
ListNode* copyHead = nullptr;
if(l1 && l2){
int val = (l1 -> val + l2 -> val) % 10;
copyNode = new ListNode(val);
carry = (l1 -> val + l2 -> val) / 10;
l1 = l1 -> next;
l2 = l2 -> next;
}
copyHead = copyNode;
while(l1 || l2 || carry){
int val = 0;
ListNode* cur = new ListNode(0);
if(l1){
cur -> val += l1 -> val;
l1 = l1 -> next;
}
if(l2){
cur -> val += l2 -> val;
l2 = l2 -> next;
}
if(carry){
cur -> val += carry;
}
carry = cur -> val / 10;
cur -> val %= 10;
copyNode -> next = cur;
copyNode = cur;
}
return copyHead;
}
};
/**
* 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) {
if(l1 == nullptr && l2 == nullptr){
return nullptr;
}
if(l1 == nullptr){
return l2;
}
if(l2 == nullptr){
return l1;
}
ListNode* node = nullptr, *head = new ListNode;
head -> val = 0;
int carry = 0;
head -> val += l1 -> val;
l1 = l1 -> next;
head -> val += l2 -> val;
l2 = l2 -> next;
if(head -> val >= 10){
head -> val = head -> val % 10;
carry = 1;
}
node = head;
while(l1 || l2 || carry){
ListNode* temp = new ListNode;
temp -> val = 0;
if(l1){
temp -> val += l1 -> val;
l1 = l1 -> next;
}
if(l2){
temp -> val += l2 -> val;
l2 = l2 -> next;
}
if(carry){
temp -> val += carry;
carry = 0;
}
if(temp -> val >= 10){
carry = 1;
temp -> val %= 10;
}
node -> next = temp;
node = temp;
}
return head;
}
};
