2.两数相加

发表于 | 分类于
字数统计: 377 | 阅读时长 ≈ 1

一、题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

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

二、题解

1.算法描述

2.个人分析

  • 定义两个指针，分别指向两个链表
  • 每访问一个节点，申请一个新节点存放该位应该存放的值，并记录进位flag
  • 循环结束后，如果仍有进位，则在申请一个新节点用来存放进位

3.代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *l3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    l3->next = NULL;
    struct ListNode *p = l1, *q = l2, *r = l3;
    int a, b, c, flag = 0;
    while (p != NULL || q != NULL)
    {
        a = p != NULL ? p->val : 0;
        b = q != NULL ? q->val : 0;
        c = (a + b + flag) % 10;
        flag = (a + b + flag) / 10;

        r->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        r = r->next;
        r->val = c;
        r->next = NULL;

        if (p != NULL)
            p = p->next;
        if (q != NULL)
            q = q->next;
    }
    if (flag)
    {
        r->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        r = r->next;
        r->val = 1;
        r->next = NULL;
    }
    return l3->next;
}