两数相加

题目

来自: https://leetcode-cn.com/problems/add-two-numbers/

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

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

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

示例:

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

Go编程实现

思路:迭代计算每位数字的和,记录进位。当全部数位和进位计算完毕,结果得到。

代码如下:

// 单向链表结构
type ListNode struct {
	Val  int
	Next *ListNode
}

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//判断是否存在操作数为 0 的特例
	if l1.Val == 0 && l1.Next == nil {
		return l2
	}
	if l2.Val == 0 && l2.Next == nil {
		return l1
	}

	result := &ListNode{}
	//迭代处理的结果节点,从第一个开始
	node := result
	// 进位
	var carry int
	// 和
	v := 0
	for {
		// 若 l1 还有,则累加,同时切换下一个l1
		if l1 != nil {
			v += l1.Val
			l1 = l1.Next
		}
		// 若 l2 还有,则累加,同时切换下一个 l2
		if l2 != nil {
			v += l2.Val
			l2 = l2.Next
		}
		//累加进位
		v += carry
		carry = v / 10 // 进位
		node.Val = v % 10 // 当前位
		// 若 l1 l2 进位都没了,结束
		if l1 == nil && l2 == nil && carry == 0 {
			break
		}
		// 构建下一个结果节点
		node.Next = &ListNode{}
		node = node.Next
		v = 0
	}

	return result
}
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

本实现在 LeetCode 上测试通过,结果为:

执行用时 : 8 ms , 在所有 golang 提交中击败了 96.84% 的用户。

内存消耗 : 4.9 MB , 在所有 golang 提交中击败了 94.01% 的用户。