Skip to content

Latest commit

 

History

History
28 lines (23 loc) · 1.57 KB

File metadata and controls

28 lines (23 loc) · 1.57 KB

2.两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解题思路

有多种情况需要考虑:

  • 两列表长度相同且最后一位相加无需进位,如l1=3 2 1,l2= 4 5 6,result=7 7 7;
  • 两列表长度不同,又分为l1长于l2和l2长于l1两种情况;
  • 最后一位相加需要进位,此时又分列表长度是否相同的情况,如l1=5,l2=5或l1=5,l2=5 9;

如果考虑这么多种情况,则需要写很多if语句,可以考虑进行简化:

  • 关于列表长度:不管列表长度是否相同,在需要进行运算并且下个节点为空时,应该进行补零操作,这个思路类似小学时用竖式加法运算的思路。
  • 关于是否运算:当两个列表都是空,并且没有进位时,才能停止运算。
  • 关于输出:直接将结果放在l1中进行输出即可。

遇到的坑

  • 输出:由于是单链表,需要先记录最开始的l1作为输出的起点,否则运算结束后回不来。
  • 判断:要对是否进行运算与列表是否为空分清楚,否则容易出现未加保护或者多加保护的问题。