2_两数相加

类型：链表

• 2. 两数相加 💛

  https://leetcode-cn.com/problems/add-two-numbers/

  ❓ 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

  示例：

  

  输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.

  💡 模拟

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
      def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
          if not l1 and not l2:
              return None
          elif not l1:
              return l2
          elif not l2:
              return l1
  
          def unitAdd(node1, node2, carry, preSum):
              if not node1 and not node2 and not carry:
                  return
              val1 = node1.val if node1 else 0
              val2 = node2.val if node2 else 0
              unitSum = val1 + val2 + carry
              if unitSum > 9:
                  unitSum -= 10
                  carry = 1
              else:
                  carry = 0
              preSum.next = ListNode(unitSum)
              node1 = node1.next if node1 else None
              node2 = node2.next if node2 else None
              preSum = preSum.next
              unitAdd(node1, node2, carry, preSum)
  
          dummyHead = ListNode()
          carry = 0
          unitAdd(l1, l2, carry, dummyHead)
          return dummyHead.next

  时间复杂度：O(max(m, n))，空间复杂度：O(1)