题目描述
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.
样例
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
算法1
(暴力枚举) O(n2)
class Solution {
public:
ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int plus = 0; //用来递进,用来判断是否要进位
//int sum = 0;
ListNode l3head = new ListNode(-1), *l3 = l3head; //new构造传递了一个指针回去
/*
ListNode l3head = *(new ListNode(-1)), *l3 = &l3head;
…
…//这样也是可以的
return l3head->next; //
*/
while(l1 != nullptr || l2 != nullptr || plus != 0 ){//plus放在这是为了防止最后一位还要进位
if( l1 != nullptr ){
plus += l1->val; //这是个循环,所以plus都是 +=
l1 = l1->next;
}
if(l2 != nullptr){
plus += l2->val;
l2 = l2->next;
}
l3->next = new ListNode(plus%10);//取余并求进,留到下一个用
l3 = l3->next;
plus /= 10;
}
return l3head->next;
}
};
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
blablabla