链表-两数相加
问题
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头
示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
在看解法之前，请大家先思考下，自己该怎么解决呢
解法一
我们看题目和上面示例，很明显能得到下面一张图，上面示例是342+465，那么得是先从2+5=7，放入新链表的末尾，以此向下进行，放入新链表的头部，遇到相加大于10的进1。最后对链表反转得到的结果就是正确答案，如第一张图，我们接着看，2+5=7，4+6=10进1，3+4+1 =8，从前往后放结果是不是反转也不需要了，直接就是答案了？确实如此，如第二张图
下面我们开始进入编程思路，首先声明一个链表
type ListNode struct {
Next *ListNode
Val int
}我们想到链表相加不太友好，而且考虑到两个链表长度不一样呢（比如A链表 1->2->3, B链表 4->5），所以我将链表转化为数组，长度短的补零，如举例的AB链表转化后，如下图
func buildArray(node1 *ListNode, node2 *ListNode) ([]int ,[]int ) {
array1 := make([]int,0)
array2 := make([]int,0)
for node1 != nil{
array1 = append(array1,node1.Val)
node1 = node1.Next
}
for node2 != nil{
array2 = append(array2,node2.Val)
node2 = node2.Next
}
l := len(array1)
r := len(array2)
// 如果array1的长度小于array2的长度，那么array1补0，直到和array2相等
for l < r{
array1 = append(array1,0)
l++
}
// 如果array2的长度小于array1的长度，那么array2补0，直到和array1相等
for r < l{
array2 = append(array2,0)
r++
}
return array2,array1
}接着我们按照分析对数组进行相加，得到一个新的数组，考虑一下，新数组的长度考虑建多长呢？两个三位数相加（999+999 = 1998），最大是4位数，所以新数组的长度永远比原来数组的长度大1就可以，看代码：
func sumArray(array1 []int, array2 []int) []int {
//新的数组（长度为原数组长度+1，因为两个三位数相加的和可能是4位数）
result := make([]int,len(array1)+1)
//temp变量是新数组的下标,从0开始
for i,temp:=0,0;i<len(array1); i++{
//对两个数组相加
sum := array1[i]+array2[i]
//想一想为啥sum又要加上新数组的下标呢？
sum = result[temp] + sum
if sum < 10{
result[temp] = sum
temp++
continue
}
//如果大于10，需要往上进一位
//把个位数字放入当前位置
result[temp] = int(sum % 10)
//把十位数字放入下一个位置，所有才有上面的sum = result[temp]+sum
result[temp+1] = int(sum / 10)
temp++
}
return result
}最后我们对结果进行组装成一个新的链表
func createNewListNode(result []int) *ListNode {
var head,m *ListNode = nil,nil
for i:=0;i<len(result);i++{
if result[i] ==0 && i == len(result)-1{
break
}
if m== nil{
m = &ListNode{Val:result[i],Next:nil}
head = m
continue
}
m.Next = &ListNode{Val:result[i],Next:nil}
m = m.Next
}
return head
}最后对上面三个步骤组合，得到结果
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
//把链表构造为两个数组
array1,array2 := buildArray(l1,l2)
//对数组相加
result := sumArray(array1,array2)
//组装新的链表
return createNewListNode(result)
}解法二
看完上面的解法一，为什么这么复杂？脑袋疼，想不过来，不想学算法了，有没有更简单的，解法二带你体验算法的神奇魅力。从解法一我们得知是从链表头部开始相加，所得结果最后作为新链表的头部，如果大于10，则向上进一位，在创建新链表下一个节点时把进上来的值加上，依次直到两个链表的节点都为空，基于这个我们考虑能不能用递归呢？
递归入参是，node1，node2， result[]int (存储链表节点的值的和)，carry(进位的值)
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{
result := make([]int,0)
//递归求值
result = sumListNode(l1,l2,result,0)
var head,temp *ListNode = nil,nil
// 组装新的链表
for i:=0;i<len(result);i++{
if temp == nil{
temp = &ListNode{Val:int(result[i]),Next:nil}
head = temp
continue
}
temp.Next = &ListNode{Val:result[i],Next:nil}
temp = temp.Next
}
return head;
}
func sumListNode(node1 *ListNode, node2 *ListNode, result []int,carry int) []int {
//当两个节点都为空，计算完毕
if node1 == nil && node2 == nil{
//判断节点最后的和进位是否有值
if carry != 0{
result = append(result,carry)
}
return result
}
//两个节点的值初始都置为0(跟解法一中链表构造数组长度不一致补0是一个思路)
l1,l2 := 0,0
if node1 != nil{
//重新赋值
l1 = node1.Val
node1 = node1.Next
}
if node2 != nil{
//重新赋值
l2 = node2.Val
node2 = node2.Next
}
//求和
temp := l1 + l2 + carry
//取域
remainder := temp % 10
//求商（也是进位，大于10是进位是1，否则是0）
carry = temp / 10
//将求的和放入数组中
result = append(result,remainder)
//递归求两个链表的下一个节点的和
return sumListNode(node1,node2,result,carry)
}最后，希望大家有所收获，如果大家有更好的思路可以留言交流，同时大家可以思考下这两种方法的空间复杂度和时间复杂度。
腾讯云开发者
