445.两数相加 II

一、题目描述

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

你可以假设除了数字 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最快的一次,哈哈哈哈哈哈哈!

先埋下这个坑,日后再来填!😝