首页 > 其他 > 详细

Add Two Numbers

时间:2018-07-20 22:05:36      阅读:46      评论:0      收藏:0      [点我收藏+]

标签:另一个   present   reverse   turn   直接   什么   order   tar   numbers   

原题:

  You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

题目大意:给出两个链表,存储非负数,两个链表都是按倒序方式存储数字(个位,十位,百位……)要求将两个链表相加并以链表形式返回。

回顾下链表的基础知识概念:

① 什么是链表?

举个例子:在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就非常麻烦,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我们会怎么做?当然是将5之后的数据往后退一位,然后再插入4,这样非常麻烦,效率也非常低,但是如果用链表,我就直接在3和5之间插入4就行。

链表由一个个节点连接而成,节点结构如下:

技术分享图片

其中data部分(数据域)存储数据,next部分(指针域)存储指针,指向下一个节点。任一个链表开始于头指针head,头结点的数据域可以不存储数据。

② 链表基本操作?

初始化链表、链表长度、插入、删除、新增、查找、逆序。具体就不展开了~

解答:

注意以下几个小问题:

 链表不同于列表数组之类的,不能用len()获取长度

★ 既要考虑到了存在的进位情况,也要考虑到链表长度不等,即两个加数位数不等(比如三位数加五位数)

我们可以考虑将题目拆分为两个情况,以三位数加五位数为例,前三位数和前三位数按照我们已有的思路进行处理,第四位第五位则是另一种情况;具体就是:前三位数范围内,对应位进行相加操作时附加上低位的进位;第四位第五位只用将该位加上低位的进位即可(或者理解成另一个三位数的高位为0)具体代码实现如下:

 

Add Two Numbers

标签:另一个   present   reverse   turn   直接   什么   order   tar   numbers   

原文:https://www.cnblogs.com/tianqizhi/p/9343720.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号