网站首页 返回列表 像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。 leetcode基础算法学习之addTwoNumbers 18-10-19 13:40:19 云丶先生 258 ### 习题二： 您将获得两个非空链表，表示两个非负整数。数字以相反的顺序存储，每个节点包含一个数字。两个数字相加并将其作为链表返回。您可以假设这两个数字不包含任何前导零，除了数字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 18-10-30 08:54 aaaa efg 18-10-30 16:57 引用 网友 efg：aaaa 不好意思，胡乱写了一条评论 最新文章 虹口区财政局2026年代理记账资格行政许可决定公示 关于公开征集网络餐饮食品安全违法违规线索的公告 2026年虹口区劳动人事争议仲裁院辅助人员招聘公告 2026年4月虹口区应急管理综合行政执法对象和执法事项公示 虹口区财政局 2026 年代理记账资格行政许可决定公示 上海市虹口区人民政府关于上海港国际客运中心口岸限定区域范围及管理要求的通告 虹口区98街坊HK381-05地块新建学校项目方案公示公告 虹口区广中社区N080601单元控制性详细规划077街坊局部调整公众参与草案补充公示 点击排行 站点又重新回来了，必须纪念一下本次事故 Beego框架第1节——环境与初始 Golang学习笔记之interface Golang学习笔记之匿名函数与闭包 leetcode基础算法学习之addTwoNumbers 最新评论 efg 7年前 不好意思，胡乱写了一条评论 efg 7年前 aaaa kakafu 7年前 good 云丶先生 官方 7年前 你好，可以，麻烦你的站点做好友链 云丶先生 官方 7年前 欢迎各界人士留言，请不要胡乱填写，尊重他人就是尊重... 友情链接 四方支付系统,聚合支付系统,三方支付系统,支付系统源码 支付系统开发,四方支付系统,支付系统源码
2 条评论 1 人参与