Golang算法之两数相加

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 808

两数相加，中等难度，leetcode地址：https://leetcode-cn.com/problems/add-two-numbers

1.描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

2.题解

这题乍一看有点懵，不是很清楚到底要干啥，又是链表又是相加，我刚开始也是这感觉

有人可能会错误的理解这题的意思就是把2个数相加，比如 243 + 564，结果应该是807，然后把结果以链表的形式反过来刚好是708

上面这种想法也不完全对，比如按照题目，249和5649的正确结果是70401，这是咋得来的呢？其实是反过来加，342+9465=10407,然后反转过来刚好。

所以有一种解决方式就是把2个链表表示的数字转换成整数再相加，最后反转，理论上没问题的，但是这种方式效率也不高，而且并不是题目考察的重点。

为了答题我们需要对链表的结构有一定了解，题目给出了链表节点的定义，是一个单向链表：

1
2
3
4
type ListNode struct {
    Val  int
    Next *ListNode
}

对于2个链表：

1
2
3
4
2 ---> 4 ---> 9
5 ---> 6 ---> 4 ---> 9
+
7 ---> 0 ---> 4 ---> 0 ---> 1

我们可以把249看作是2490，从左向右，依次相加，第一位是2+5=7，然后6+4=10，需要进位，留0进1，所以第二位数字是0，接着9+4=13，留3进1，加上前面的进位，所以第三位是4，后面依次类推。。。

参考代码:

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
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var p, head *ListNode // 定义临时节点和头节点
    var carry = 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10 // carry是进位，比如8+9=17，进1余7，%10是求余, /10是求倍
        if p == nil {
            p = &ListNode{Val: sum} //如果p为nil，则是头节点，我们需要保存头节点用于返回值
            head = p
        }else {
            p.Next = &ListNode{Val: sum}
            p = p.Next
        }
    }
    if carry > 0 { // 循环之后，需要把最后进位补齐
        p.Next = &ListNode{Val: carry}
    }
    return head
}

为了测试这段代码，我们需要创建2个链表，然后打印结果，测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func main() {
    l1 := ListNode{Val: 2}
    l1.Next = &ListNode{Val: 4}
    l1.Next.Next = &ListNode{Val: 9}

    l2 := ListNode{Val: 5}
    l2.Next = &ListNode{Val: 6}
    l2.Next.Next = &ListNode{Val: 4}
    l2.Next.Next.Next = &ListNode{Val: 9}

    node := addTwoNumbers(&l1, &l2)

    fmt.Printf("%v\n", node)
    fmt.Printf("%v\n", node.Next)
    fmt.Printf("%v\n", node.Next.Next)
    fmt.Printf("%v\n", node.Next.Next.Next)
}