dsfds' blog

学海无涯，回头是岸

0%

LeetCode | 2 两数相加

发表于 更新于 分类于 Valine：

题目

给定两个非空链表表示两个非负整数，位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加并返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以 0 开头。

示例

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

题解

这是一道链表题，我们对单链表的节点定义如下：

1
2
3
4
typedef struct NODE{
    int val;
    struct NODE *next;
} ListNode;

链表是逆序表示数字的，这对我们执行加法操作非常有利，因为在进行加法运算时，我们习惯从低位开始执行，并向高位进行进位。事实上如果它是顺序表示数字的话，我们也该想到将它进行逆序。

正确完成算法的关键在于把进位考虑进去，而且需要注意到在单链表中执行插入操作时，最快的插入位置是从表头插入，但是这样插入我们得到的结果是顺序的，之后再反转单链表即可。

以示例中的例子为例，来看看算法的执行过程。初始化进位值 carry 和待保留值 tmp，两个指针 p1 和 p2 分别指向两个链表的头部，对应的值为 2 和 5；2 + 5 = 7，故 tmp = 7，carry = 0，将 7 插入结果链表得到 7；指针分别向后移动；4 + 6 = 10，故 tmp = 0，carry = 1，将结果 0 插入链表得到 0->7；指针分别向后移动；3+4+carry=8，故 tmp=8，carry=0，将结果插入链表得到 8->0->7；然后对结果链表进行反转得到最终的结果 7->0->8。

上述的是一个典型的执行过程，实际上还有一些其他情况需要考虑，如输入两个链表的长度并不一样，计算完时 carry 不为 0。对于前者，我们在上述环节之外在添加两个处理过程即可，如第 17 行和 26 行所示。对于后者，我们只需在反转链表前加一个判断，当进位值不为 0 时，在结果链表的头部插入一个节点即可，如 36 行所示。

最终我们得到的代码如下所示，算法的时间复杂度为 O(m+n)。

LeetCodeSolution2.cview raw
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
ListNode *addTwoNumbers(ListNode *num1, ListNode *num2)
{
    ListNode *theSum, *p = NULL;
    int tmp = 0;   // 保存值
    int carry = 0; // 进位
    while (num1 && num2) {
        tmp = (num1->val + num2->val + carry) % 10;
        carry = (num1->val + num2->val + carry) / 10;
        theSum = (ListNode *)malloc(sizeof(ListNode));
        theSum->val = tmp;
        theSum->next = p;
        p = theSum;
        num1 = num1->next;
        num2 = num2->next;
    }
    // 链表长度不同
    while (num1) {
        tmp = (num1->val + carry) % 10;
        carry = (num1->val + carry) / 10;
        theSum = (ListNode *)malloc(sizeof(ListNode));
        theSum->val = tmp;
        theSum->next = p;
        p = theSum;
        num1 = num1->next;
    }
    while (num2) {
        tmp = (num2->val + carry) % 10;
        carry = (num2->val + carry) / 10;
        theSum = (ListNode *)malloc(sizeof(ListNode));
        theSum->val = tmp;
        theSum->next = p;
        p = theSum;
        num2 = num2->next;
    }
    // 最后进位值不为 0
    if (carry) {
        theSum = (ListNode *)malloc(sizeof(ListNode));
        theSum->val = carry;
        theSum->next = p;
    }
    theSum = reverseLinkedList(theSum);
}
// 反转链表
ListNode *reverseLinkedList(ListNode *head)
{
    ListNode *p = NULL, *q;
    while (head) {
        q = head->next;
        head->next = p;
        p = head;
        head = q;
    }
    return p;
}