目录：
目的
思路
复杂度
记忆秘诀
python代码
目的
链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0
思路
这个任务是相加两个链表的数值。就像手算加法过程一样。两个链表表示两个整数，每个节点代表一位数字。从右到左开始相加（两个链表反转），遇10进1，最后得到两数之和（结果链表再反转）。
准备阶段：
-
反转链表：准备从低位开始加：
head1 = self.reverseList(head1)
head2 = self.reverseList(head2)-
链表反转：参考文章
力扣刷题TOP101：1.BM1 反转链表-CSDN博客
-
-
准备一个虚拟节点，方便构造结果链表：
carry = 0 # 进位值，一开始为 0
dummy = ListNode(0) # 虚拟头节点，用于方便操作结果链表
current = dummy # 指向当前结果的位置
相加过程：逐位相加，处理进位
这个循环就是在模拟小学数学中的逐位加法：
- 如果链表还有值，取当前节点的值；否则取
0val1 = head1.val if head1 else 0
val2 = head2.val if head2 else 0
- 计算当前位的和，还要加上进位carry
total = val1 + val2 + carry- 传递当前进位，carry = total // 10
- 将当前位的值放入结果链表，current.next = ListNode(total % 10)
current移动到结果链表的下一位准备current = current.next
head1和head2分别移动到对应输入链表的下一位if head1: head1 = head1.next
if head2: head2 = head2.next
相加结果：
-
当
head1和head2都遍历完（即head1 == None and head2 == None），且 没有进位（carry == 0），循环条件为False，此时退出循环。 -
反转结果链表（目前是低位到高位），因为我们最后输出的结果是从高位到低位。
复杂度
-
时间复杂度：O(n）
- 其中 n 为较长的链表长度，因为我们需要遍历每个链表两次（一次反转，一次相加）。
-
空间复杂度：O(1)
- 只使用了常数额外空间来存储指针和进位。
记忆秘诀
- 反转链表：从个位开始计算。
- 逐位相加：处理每一位和可能的进位。
- 恢复顺序：最后把结果调整成从高位到低位的正确排列。
python代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head1 ListNode类
# @param head2 ListNode类
# @return ListNode类
#
class Solution:# 工具函数：反转链表def reverseList(self, head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prevdef addInList(self, head1: ListNode, head2: ListNode) -> ListNode:# 1. 反转两个链表head1 = self.reverseList(head1)head2 = self.reverseList(head2)carry = 0 # 进位dummy = ListNode(0) # 结果链表的虚拟头节点scurrent = dummy# 2. 逐位相加，处理进位while head1 or head2 or carry:val1 = head1.val if head1 else 0val2 = head2.val if head2 else 0total = val1 + val2 + carrycarry = total // 10 # 计算进位current.next = ListNode(total % 10) # 将当前位的值放入结果链表current = current.nextif head1: head1 = head1.nextif head2: head2 = head2.next# 3. 反转结果链表return self.reverseList(dummy.next)
* 欢迎大家探讨新思路，能够更好的理解和记忆