网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

leetcode基础算法学习之addTwoNumbers

2018-10-19 13:40:19 admin 1004

### 习题二：
您将获得两个非空链表，表示两个非负整数。数字以相反的顺序存储，每个节点包含一个数字。两个数字相加并将其作为链表返回。您可以假设这两个数字不包含任何前导零，除了数字0本身。
Input: `(2 -> 4 -> 3) + (5 -> 6 -> 4)`
Output: `7 -> 0 -> 8`
Explanation: `342 + 465 = 807`

### 解题思路
- 基本思路：
两个数值使用单链表来存储，链表每一个节点存储一个数字，从链表头开始，由低位到高位。如把两个链表都遍历一遍，算出所表示的数值，然后相加得到答案后再构建要返回的链表，这显然是不合理的，最好的解决办法一定是依靠链表的结构与所有位数数字相加进位来处理。首先是单个数字最大是9，那么算上上一位的进位，当前向高位的进位值最大是`1+9+9=19`，因此进位要么是1，要么就是0。
- 考虑特殊情况：
	+ 当一个列表比另一个列表长时。
	+ 当一个列表为空时。
	+ 总和之后可能会出现多1进位，这很容易忘记。如99+1=100

### 实现代码
```go
package main

import "fmt"

type ListNode struct {
	Val int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var dummyHead = &ListNode{}
	var p, q = l1, l2
	var curr = dummyHead
	var carry int
	for p != nil || q != nil {
		x, y := 0, 0
		if p != nil {
			x = p.Val
		}
		if q != nil {
			y = q.Val
		}
		sum := x + y + carry
		carry = sum / 10
		curr.Next = &ListNode{sum % 10, nil}
		curr = curr.Next
		if p != nil {
			p = p.Next
		}
		if q != nil {
			q = q.Next
		}
	}
	if carry > 0 {
		curr.Next = &ListNode{carry, nil}
	}
	return dummyHead.Next
}

func main() {
	l1 := &ListNode{2, &ListNode{4, &ListNode{3, nil}}}
	l2 := &ListNode{5, &ListNode{6, &ListNode{4, nil}}}
	fmt.Println(addTwoNumbers(l1, l2))
	fmt.Println(addTwoNumbers(l1, l2).Next)
	fmt.Println(addTwoNumbers(l1, l2).Next.Next)
}
```

### 代码总结
- 首先定义好单链表结构，该结构是原出题者在题目中已经有所提示，按题目要求，函数应接收2个单链表，返回1个相加之后的单链表。
- 第11行初始化一个临时容器`dummyHead`，在leetcode上称之为虚拟头，该容器指向一个内存地址，同时指定当前动态容器`curr`也为该指针，第25行当`curr.next`有改变时，同时代表着`dummyHead.next`在改变，而第26行`curr`自身的指针被重写绑定刚刚改变的`dummyHead.next`指针。
- 第15行为了排除特殊情况1和2，让接收的2个链表一直循环到`nil`为止，任何1个链表没有`nil`都将进入循环。
- 第34行为了排除特殊情况3，当循环结束时进位`carry`变量大于0时，则最后添加一个val=carry的新实例指针即可。
- 最后强调一下，该习题所考核的重点是如何巧妙利用指针以及非常常用的整除求余（8%10=8, 12%10=2）与进位算法（12/10=1, 9/10=0），这在今后的项目实战中可能会经常用到。

关键字词算法

分享到：

上一篇：leetcode基础算法学习之FindIndex

下一篇：leetcode基础算法学习之LongestSubstr

如需留言，请登录，没有账号？请注册

2 条评论 1 人参与

efg 2018-10-30 08:54

aaaa

efg 2018-10-30 16:57

引用网友 efg：aaaa

不好意思，胡乱写了一条评论

网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

leetcode基础算法学习之addTwoNumbers

efg 2018-10-30 08:54

efg 2018-10-30 16:57

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

武云 2年前

网站首页 返回列表 像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

leetcode基础算法学习之addTwoNumbers

efg 2018-10-30 08:54

efg 2018-10-30 16:57

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

武云 2年前

网站首页返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。