LeetCode刷题计划——2.两数相加

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


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

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

需要注意的是:

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

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


拓展:如果两个链表是从最高位正序排序,如何处理?

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

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

原文地址:https://www.cnblogs.com/AI-U/p/10416428.html