【算法设计与分析作业题】第一周:2. Add Two Numbers
程序员文章站
2022-03-14 11:01:37
...
题目
C++ solution
/**
* 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* resultList = NULL; // 存储结果List
ListNode* tempNode = NULL; // 临时节点,用于在结果List中插入新节点
// 加法运算,若其中一个的位数全部加完,补充前导0继续加,直到两个数字的位数全部加完
while(l1 != NULL || l2 != NULL)
{
int val1 = l1 == NULL ? 0 : l1->val;
int val2 = l2 == NULL ? 0 : l2->val;
int new_val = val1 + val2 + carry;
// 判断是否进位
if(new_val > 9)
{
carry = 1;
new_val -= 10;
}
else
{
carry = 0;
}
if(resultList == NULL)
{
resultList = new ListNode(new_val);
tempNode = resultList;
}
else
{
tempNode->next = new ListNode(new_val);
tempNode = tempNode->next;
}
l1 = l1 == NULL ? NULL : l1->next;
l2 = l2 == NULL ? NULL : l2->next;
}
if(carry == 1)
{
tempNode->next = new ListNode(carry);
}
return resultList;
}
};
简要题解
按照加法运算算法,将两个数从低位到高位逐位相加,若和大于或等于10,则向前进位;若其中一个数的位数全部加完,补充前导0继续加,直到两个数的位数全部加完;此时若有进位,则将进位加到运算结果中;运算结束。