Leetcode 002 题
Difficulty:Medium
Tag: Linked List, Math
Add two numbers
大致题意
原题目链接 ： https://leetcode.com/problems/add-two-numbers/?tab=Description
给定两个链表，每个链表都表示一个非负整数，这个整数数的每一位都是按照逆序存储在链表的节点上，且每个节点只能存储一个位信息。
比如
整数 342，用这种链表表示应该是 2 -> 4 -> 3 。
例子
两个链表分别表示整数 342 和 475. 根据题意
链表 ( l_1: 2 -> 4 -> 3 )
链表 $ l_2: 4 -> 7 -> 5 $
两数相加的结果为
$ 7 -> 1 -> 8 $
解析
这其实一个两个链表相加的问题，只不过进位需要向右传播。
如上图所示： 依次计算每一位，由于有进位的存在，所以还要加上前一位的进位：
计算过程如下：
第一位 $ result_0 = 2 + 5 + carry_0 (carry_0 = 0) $
进位 $ carry_1 = result_0 / 10$
第二位 $ result_1 = 2 + 5 + carry_1 $
进位 $ carry_2 = result_1 / 10$
第三位 $ result_2 = 2 + 5 + carry_2 $
进位 $ carry_1 = result_2 / 10$
明显是一个迭代算法，每次迭代更新 result 和 carry 即可。
代码如下：
/**
* 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) {
ListNode result(0);
ListNode* p = &result;
int carry = 0;
while(l1 || l2)
{
int res = carry + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
carry = res / 10;
res = res % 10;
p->next = new ListNode(res);
p = p->next;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
if(carry)
{
p->next = new ListNode(carry);
p = p->next;
}
return result.next;
}
};
时间复杂度
整段程序只有一个while循环，所以是线性的时间复杂度 $O(n)$.
具体的值：假设 $m$和$ n $ 分别为$l_1$, $l_2$的长度，while循环执行的次数取决于 $m$和$ n $ 最大的那个，时间复杂大具体为 $O(max(m, n))$