给定两个非空链表，表示两个倒叙排序的非负的正整数，每个节点代表正整数的一位，给出一个新链表，表示两个数相加的和。

---

 

典型的大数相加问题，按大数相加的思想逐位相加，保存进位即可。

时间复杂度O(max(m,n))，两个链表各遍历一遍；空间复杂度O(1)

需要注意的是：

如果两个链表长度不同，要记得处理长链表剩下节点。

如果两个链表所有节点均处理完毕之后，还有进位，要把进位也输出。

---

 

拓展：如果两个链表是从最高位正序排序，如何处理？

使用栈，利用栈的后进先出原理，变成倒序处理。

时间复杂度O(2*max(m,n))，两个链表各遍历一遍；空间复杂度O(m+n)