445.两数相加 II

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

一、题目描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

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

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

1
2
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

二、题解

1.算法描述

  • 反转链表+逐位相加

2.个人分析

这道题我本来还没思路，结果进阶说：不能翻转怎么办？

还能怎么办，我不进阶了，哈哈哈哈哈哈，快乐就完事了！😂

（直接把第2题和第206题的代码粘过来了）

直接：反转、反转，相加，反转

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *reverseList(struct ListNode *head)
{
    struct ListNode *p, *q, *r;
    p = head;
    r = NULL;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        q->next = r;
        r = q;
    }
    return r;
}

struct ListNode *addTwo(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;
}
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2)
{
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    return reverseList(addTwo(l1, l2));
}

我太机智了，这是我AC最快的一次，哈哈哈哈哈哈哈！

先埋下这个坑，日后再来填！😝