算法历程：两数相加

本人菜鸡一只，在算法上被各种吊锤，但其中也受到了各路大佬的帮助，为了记录自己的成长，也为了让新人收获我的经验（虽然感觉万中无一。

。

。

。

。

。

），遂记录下做题过程，因为目前比较熟练的只有go语言，所以代码部分全由go语言写成，但算法部分应该大同小异，因为水平有限，所以解法可能不是最优解，甚至可能有错误，在评论区中指出的时候希望各位大佬能笔下留情，（跪.jpg）

题目来源：力扣算法：两数相加

题目：

给你两个 非空 的链表，表示两个非负的整数。

它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例：

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

思考过程： 1、写好框架

写算法的时候，个人建议哪怕啥思路都没有，也可以试着把此算法必须的部分列出来，这对思路的整理是有好处的，哪怕多余的也不要怕，又不是不能删。

。

。

。

。

。

当然，搭好的框架可能会限制思路的发散，反而影响对题的深度思考，这点见仁见智，反正我这个菜鸡不搭框架连往哪边像都不知道。

。

。

1. 复制题目上的空函数体。
   

2. 由题可得，输入的是链表，输出的也是链表，所以就新定义个结果链表吧！
3. 节点的循环肯定也是必要的，也一同写上吧！

结果如下：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//定义链表的头节点
	l := new(ListNode)
	ll := l
	//节点的循环
	for{
		//为下一个节点申请空间
		l.Next = new(ListNode)
		//进入下一个节点
		l = l.Next
	}
}

2、根据题目写出大致功能

在题目要求非常直白或者在有思路的情况下，写出大致的功能，只要完成这一步并思路不出错，算法就算是解出来一大半了，所以这一步基本算是算法中最困难的部分，不过好在这道题很直白，所以这一步可能很轻松的想出来，至于能不能写出来就看大家对链表的熟悉程度了（因为学艺不精，本题目的链表实现部分本菜鸡翻了半天的链表相关资料才写出来的。

。

。

。

。

。

）

1. 两数相加（暂不考虑进位）。
   

2. 进入下一个节点（暂不考虑两个链表长度不一样）。
   

3. 结束循环的条件（即两个链表同时到达尾节点）。
   

结果如下：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//定义链表的头节点
	l := new(ListNode)
	ll := l
	//节点的循环
	for {
		//为下一个节点申请空间
		l.Next = new(ListNode)
		//两数相加
		l.Val = l1.Val + l2.Val
		//到达尾节点
		if l1.Next == nil && l2.Next == nil {
			return ll
		}
		//进入下一个节点
		l = l.Next
		l1 = l1.Next
		l2 = l2.Next
	}
}

3、处理细节和考虑特殊情况

这部分就看大家的思路够不够发散了，毕竟有的特殊情况真的很让人傻眼。

。

。

特殊情况1：两数相加可能会导致进位。

这个是加法的正常现象，因为一个节点只能放一位数字，所以要把多出来的一位放在结果链表的下一位，本节点结果减10（考虑通用性的话用取余%比较合适，但是毕竟这只是加法，减10也能满足条件，毕竟加法最多只会多10），因为我们是在运算前就先申请了结果链表的下一位的空间，所以直接在下一位结果链表置1即可，加法算式和结束循环因此也需要变化一下。

...
	for{
	
		...
		//两数相加
		l.Val = l1.Val + l2.Val + l.Val
		//如果两数之和大于10
		if l.Val >= 10 {
			l.Val = l.Val - 10
			l.Next.Val = 1
		}
		//如果两个链表都无下一个节点
		if l1.Next == nil && l2.Next == nil {
			if l.Next.Val == 0 {
				l.Next = nil
			}
			return ll
		}
		...
	}
...

特殊情况2：两链表长度不一样。

这个情况也很容易想到，如果只有一个下个节点为空，那就不符合循环结束的条件（毕竟不为空的那一条的数还没加上），对于我个人来说，想一个比较好实现的解决方法有点困难（毕竟菜鸡一只，很多方法以我水平很难实现），最后我想到的方法是：位数不够，0位补齐！

...
	for{
		...
		//如果两个链表都无下一个节点
		if l1.Next == nil && l2.Next == nil {
			if l.Next.Val == 0 {
				l.Next = nil
			}
			return ll
		}
		//如果单个链表无下个节点
		if l1.Next == nil {
			l1.Next=new(ListNode)
		}
		if l2.Next == nil {
			l2.Next =new(ListNode)
		}
		...
	}
...

特殊情况3：链表为空。

这个在案例里面几乎必出，搞得我一想特殊情况就能想到这个，不过这个很好解决，单独写出来个情况判断就好了！

...
	//特殊情况：其中一项为空的情况
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
...

将以上特殊情况整合起来，就是最终代码啦！

最终代码：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	//特殊情况：其中一项为空的情况
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	//定义链表的头节点
	l := new(ListNode)
	ll := l
	
	for {
		//为下一个节点申请空间
		l.Next = new(ListNode)
		//两数相加
		l.Val = l1.Val + l2.Val + l.Val
		//如果两数之和大于10
		if l.Val >= 10 {
			l.Val = l.Val - 10
			l.Next.Val = 1
		}
		//如果两个链表都无下一个节点
		if l1.Next == nil && l2.Next == nil {
			if l.Next.Val == 0 {
				l.Next = nil
			}
			return ll
		}
		//如果单个链表无下个节点
		if l1.Next == nil {
			l1.Next=new(ListNode)
		}
		if l2.Next == nil {
			l2.Next =new(ListNode)
		}
		//进入下一个节点
		l = l.Next
		l1 = l1.Next
		l2 = l2.Next
	}
}

运行结果：

至此此题结束，虽然还有很多优化的空间，但是因为水平有限，后面的优化就期待各位有志之士来实现吧！