Leetcode # 445. Add Two Numbers II

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

Solution

Time Complexity: O(max(len(l1), len(l2)))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    l_len = [0, 0]
    for i, cur in enumerate([l1, l2]):
      while cur:
        l_len[i] += 1
        cur = cur.next

    i, max_len = 0, max(l_len[1], l_len[0])
    head = carry_from = ListNode(0, ListNode())
    cur = head.next
    cur1 = l1 if i ==  max_len - l_len[0] else None
    cur2 = l2 if i ==  max_len - l_len[1] else None
    while cur1 or cur2:
      d1 = cur1.val if cur1 else 0
      d2 = cur2.val if cur2 else 0

      _sum = d1 + d2
      cur.val = _sum % 10
      if _sum // 10 > 0:
        # carry_from, Node(9), Node(9), ..., Node(9), cur
        carry_from.val += 1
        start = carry_from.next
        while start != cur:
          start.val = 0
          start = carry_from = start.next

      if cur.val < 9:
        carry_from = cur

      i += 1
      cur1 = cur1.next if cur1 else (l1 if i ==  max_len - l_len[0] else None)
      cur2 = cur2.next if cur2 else (l2 if i ==  max_len - l_len[1] else None)

      if cur1 or cur2:
        cur.next = ListNode()
        cur = cur.next

    return head if head.val > 0 else head.next

解法：逆序

Solution: Using Stack

Solution: Reverse Given Linked Lists

Last Updated on 2023/08/16 by A1go