leetcode-两数相加

leetcode-两数相加

一、题意

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

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

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

示例:

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

题目来源:leetcode-两数相加

二、分析

  • 整数的各个位置通过链表逆序连接起来,求和与笔算求和的顺序刚好相反。计算时需要考虑进位的情况。

  • 两个链表的长度可能不同,遍历完其中一个链表后,直接将未走到终点的链表链接到尾部。这个多出来的结点就是多出来的位数。

三、代码实现

main.go
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
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// Val值逆序存储
// 要考虑进位
res := &ListNode{}
cur := res
carry := 0 // 进位
for l1 != nil && l2 != nil {
sum := l1.Val + l2.Val + carry
val := sum % 10
carry = sum / 10
lnode := &ListNode{Val: val}
cur.Next = lnode
cur = cur.Next
l1 = l1.Next
l2 = l2.Next
}
// 最后无进位
if carry == 0 {
// l1比l2长
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
} else {
for l1 != nil {
sum := l1.Val + carry
val := sum % 10
carry = sum / 10
node := &ListNode{Val: val}
cur.Next = node
cur = cur.Next
l1 = l1.Next
}
for l2 != nil {
sum := l2.Val + carry
val := sum % 10
carry = sum / 10
node := &ListNode{Val: val}
cur.Next = node
cur = cur.Next
l2 = l2.Next
}
for carry != 0 {
val := carry % 10
carry = carry / 10
node := &ListNode{Val: val}
cur.Next = node
cur = cur.Next
}
}
return res.Next
}

四、测试代码

test.go
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
61
62
63
64

package problem007

import (
"fmt"
"testing"

"github.com/stretchr/testify/assert"
)

func createList(vals []int) *ListNode {
if len(vals) == 0 {
return nil
}
res := &ListNode{
Val: vals[0],
}
cur := res
for i := 1; i < len(vals); i++ {
cur.Next = &ListNode{
Val: vals[i],
}
cur = cur.Next
}
return res
}

func printList(l *ListNode) {
for l != nil {
val := l.Val
l = l.Next
if l == nil {
fmt.Printf("%d", val)
} else {
fmt.Printf("%d --> ", val)
}
}
}

func Test_addTwoNumbers(t *testing.T) {
ast := assert.New(t)
l1 := createList([]int{2, 4, 3})
l2 := createList([]int{5, 6, 4})
ans := createList([]int{7, 0, 8})
res := addTwoNumbers(l1, l2)
ast.Equal(ans, res)
fmt.Printf("输入:(")
printList(l1)
fmt.Printf(") + (")
printList(l2)
fmt.Println(")")
fmt.Printf("输出:")
printList(res)
fmt.Println()
}

// 输出如下:
=== RUN Test_addTwoNumbers
输入:(2 --> 4 --> 3) + (5 --> 6 --> 4)
输出:7 --> 0 --> 8
--- PASS: Test_addTwoNumbers (0.00s)
PASS

Process finished with exit code 0

五、总结与思考

本题和合并两个排序的链表类似,在构造链表时,都是顺序遍历两个链表。两数之和每次都是将两个链表对应的结点的值域相加,合并链表则是每次取其中值较大或者较小者。

六、C++ 实现

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
* 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)
{
// 为什么不初始化为0?初始化为1,就可以假定两个参数至少有一个节点,但是这样也不是完全的边界情况啊?
// 还是要判断下两个头结点是不是空?
if(l1 == NULL && l2 == NULL)
{
//return &ListNode{0}; // golang 的写法,在这里是不对的
return NULL; // 直接返回一个空
}
else if(l1 == NULL && l2 != NULL)
{
return l2;
}
else if(l2 == NULL && l1 != NULL)
{
return l1;
}
int len1 = 1;
int len2 = 1;
ListNode* p = l1;
ListNode* q = l2;
while(p->next != NULL)
{
++len1;
p = p->next;
}
while(q->next != NULL)
{
++len2;
q = q->next;
}
if(len1 > len2) // l1较长,在l2末尾补上0
{
for(int i = 1; i <= len1-len2; ++i)
{
q->next = new ListNode(0);
q = q->next;
}
}
if(len1 < len2) // l2较长,在l1处末尾补0
{
for(int i = 1; i <= len2-len1; ++i)
{
p->next = new ListNode(0);
p = p->next;
}
}
// 相等则不处理
// 又回到两个链表的开头,因为此时两个链表的长度肯定是相等的
p = l1;
q = l2;
bool carry = false; // 进位
ListNode* res = new ListNode(-1); // 结果指针
ListNode* cur = res; // 移动指针
int sum = 0; // 相加结果
while(p != NULL && q != NULL)
{
sum = p->val + q->val + carry; // bool值 false=0、true=1
cur->next = new ListNode(sum%10); // 生成一个新的节点保存余数
carry = sum >= 10 ? true : false;
// 都移动到下个节点
cur = cur->next;
p = p->next;
q = q->next;
}
if(carry != 0) // 如果还有进位
{
cur->next = new ListNode(1);
cur = cur->next;
}
return res->next;
}
};
评论
0 条评论
支持 Markdown 语法

来做第一个留言的人吧!


:D 一言句子获取中...