LeetCode算法-两数相加

不知不觉又是一个星期过去了，本周没有刷算法题，也没有更新博客，实在是有几分愧疚。今天来看一下LeetCode算法的第二题：两数相加。

题目描述：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

拿到题目的第一反应，就是我该去补一补链表的相关知识了[>_<]。然后，这道题的思路应该比较明确，就是通过链表来模拟加法运算。回想一下我们进行加法操作时的过程，首先是从最低位开始，对应位置的值相加，然后是下一位相加，当前一位相加后有进位时，下一位的相加结果同时要加上上一位的进位…以此循环直到最高位。伪代码大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
1 定义一个单节点phead，并将其值初始化为0，并将当前节点 ``curr`` 指向该节点；  
2 将节点 ``p`` 和 ``q`` 分别指向列表 ``l1`` 和 ``l2`` 的头节点；  
3 将进位 ``carry`` 初始化为0；  
4 遍历 ``l1`` 和 ``l2`` 直至其尾端：  
  4.1 将 ``x`` 的值设为节点 ``p`` 的值，若节点 ``p`` 已经到达列表 ``l1`` 的尾端，则取 ``x`` 的值为0；  
  4.2 将 ``y`` 的值设为节点 ``q`` 的值，若节点 ``q`` 已经到达列表 ``l2`` 的尾端，则取 ``y`` 的值为0；  
  4.3 求和 ``sum = x + y + carry`` ；  
  4.4 更新进位 ``carry = sum / 10`` ；  
  4.5 创建值为 ``sum % 10`` 的新节点，将其设置为当前节点的下一节点，同时将当前节点前移;  
  4.6 将节点 ``p`` 和 ``q`` 前移到下一节点；  
5 检查 ``carry`` 是否还有进位，若还有进位，则再增加一个值为1的节点；  
6 返回head节点的下一个节点。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* 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* head = new ListNode(0);
        ListNode *p = l1, *q = l2, *curr = head;
        int carry = 0;
        while (p != NULL || q != NULL) {
            int x = (p != NULL) ? p->val : 0;
            int y = (q != NULL) ? q->val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            if (p != NULL) p = p->next;
            if (q != NULL) q = q->next;
        }
        if (carry > 0) {
            curr->next = new ListNode(carry);
        }
        return head->next;
    }
}

复杂度分析：
时间复杂度：O(max(m, n))。
空间复杂度：O(max(m, n))。

总结：
好好学习链表的相关知识。

附：完整代码