题目链接:https://leetcode.com/problems/add-two-numbers/

题目大意:给出两个非空链表,以数位逆序的形式分别表示两个非负整数(每个结点代表一位数字),需要将这两个数相加,并且同样以链表的形式返回。(除非本身是 0 这个数, 否则用链表表示的两个数均没有前置 0.)

思路一:Simulation

直接用链表操作进行加法模拟,下图来自官方题解:

Illustration of Adding two numbers
图示 $342+456=807$

可以得到比较直观的写法:

需要注意几点:

  • 在链表中为了方便记录初始头结点的位置,通常会引入虚拟头结点 dummy 并且让其 next 指针指向 head 结点, dummy.next 经常被用作返回值;
  • 注意结点为空的情况,以及何时才是真正的循环终止条件。
  • 加法进位 carry 的作用可以比较巧妙地用 sum 代替(对比上下代码)。

有些时候一些题解为了压缩代码行数会用到各种奇技淫巧,但整体可读性还是很重要的。

时间复杂度:$O(\max (l1, l2))$

空间复杂度:$O(\max (l1, l2))$