网站开发加盟,如何制作网络平台,免费建社交网站,数字营销工具文章目录 1. 题目2. 思路及代码实现#xff08;Python#xff09;2.1 模拟迭代2.2 递归 1. 题目
给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xff0c;并且每个节点只能存储 一位 数字。
请你将两个数相加#xff0c… 文章目录 1. 题目2. 思路及代码实现Python2.1 模拟迭代2.2 递归 1. 题目
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。
示例 1
输入l1 [2-4-3], l2 [5-6-4] 输出[7-0-8] 解释342 465 807.
示例 2
输入l1 [0], l2 [0] 输出[0]
示例 3
输入l1 [9-9-9-9-9-9-9], l2 [9-9-9-9] 输出[8-9-9-9-0-0-0-1] 提示
每个链表中的节点数在范围 [1, 100] 内节点处的值的取值范围 0 N o d e . v a l Node.val Node.val 9题目数据保证列表表示的数字不含前导零
2. 思路及代码实现Python
题解来源力扣官方题解
2.1 模拟迭代
由于输入的两个链表都是逆序存储数字的位数的因此两个链表中同一位置的数字可以直接相加。
同时遍历两个链表逐位计算它们的和并与当前位置的进位值相加。具体而言如果当前两个链表处相应位置的数字为 n 1 , n 2 n1,n2 n1,n2进位值为 carry \textit{carry} carry则它们的和为 n 1 n 2 carry n1n2\textit{carry} n1n2carry其中答案链表处相应位置的数字为 ( n 1 n 2 carry ) m o d 10 (n1n2\textit{carry}) \bmod 10 (n1n2carry)mod10而新的进位值为 ⌊ n 1 n 2 carry 10 ⌋ \lfloor\frac{n1n2\textit{carry}}{10}\rfloor ⌊10n1n2carry⌋。
如果两个链表的长度不同则可以认为长度短的链表的后面有若干个 000 。此外如果链表遍历结束后有 carry 0 \textit{carry} 0 carry0还需要在答案链表的后面附加一个节点节点的值为 carry \textit{carry} carry。
需要遍历的次数为两个链表中的较长值时间复杂度为 O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n)) m , n m,n m,n分别为两个链表的长度而空间复杂度为 O ( 1 ) O(1) O(1)不随着链表长度而增加内存占用。
from typing import Optionalclass ListNode:def __init__(self, value0, nextNone):self.val valueself.next nextdef print_linked_list(head):current headwhile current:print(current.val, end )current current.next在下面的代码中创建了一个 cur dummy ListNode() 对象其中 cur 用来不断迭代指向链表的下一个节点而 dummy 作为哨兵节点仅标记着最一开始的 ListNode() 对象因此最后返回的 dummy.next 是结果链表的头节点。
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:cur dummy ListNode()carry 0 # 初始进位为0while l1 or l2 or carry: # 只要链表不空就继续迭代carry (l1.val if l1 else 0) (l2.val if l2 else 0)cur.next ListNode(carry % 10) # 指向下一个节点carry // 10 # 更新进位cur cur.next # 将指针移到下一个节点if l1: l1 l1.next # l1 不空则移到下一个节点为空则在上面会取0if l2: l2 l2.nextreturn dummy.next # 哨兵节点示例
node4 ListNode(4)
node3 ListNode(3, node4)
node2 ListNode(2, node3)
node1 ListNode(1, node2)node44 ListNode(7)
node33 ListNode(3, node44)
node22 ListNode(2, node33)
node11 ListNode(2, node22)res Solution().addTwoNumbers(node1, node11)
print(print_linked_list(res))3 4 6 1 1 None执行用时52 ms 消耗内存17.11 MB
2.2 递归
如上述的迭代我们很容易发现从两个链表的头节点出发按位计算操作都是类似的都是进位加上 n 1 n 2 n1n2 n1n2与10的余数作为相加后的结果与10的商地板除法作为新的进位 c a r r y carry carry这可以理解为一个递归问题。
有个注意的点是在递归时为了简化代码需基于较长的链表进行递归但不需要把链表的数都取出来只需要在递归过程中当某一链表的下一节点为空时链表的节点取完了即为较短链表交换两个链表的标签即可。
递归的最底部是当两个链表都为空时此时如果 c a r r y carry carry 如果不为空则创建一个值为 c a r r y carry carry 的节点反之则为 None时间复杂度为 O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))取决于较长链表的长度而由于递归需要存储栈空间复杂度也为 O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))栈深也取决于较长的链表长度。
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry0) - Optional[ListNode]:if l1 is None and l2 is None: # 递归边界l1 和 l2 都是空节点return ListNode(carry) if carry else None # 如果进位了就额外创建一个节点if l1 is None: l1, l2 l2, l1carry l1.val (l2.val if l2 else 0)l1.val carry % 10l1.next self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)return l1执行用时52 ms 消耗内存16.93 MB
参考题解灵茶山艾府
