Leetcode # 2. Add Two Numbers

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

Solution

可能由 Multiple Assignment 引發的錯誤

	cur.next, cur = ListNode(1), cur.next 計算 ListNode(1), cur.next cur.next ← ListNode(1) cur ← cur.next != cur.next == ListNode(1)
	cur.next = ListNode(1) cur = cur.next

追加 node 適切的方式

	如果每次都在迴圈中追加新的 cur.next = ListNode() 然後等到下一次的迴圈才計算 cur.val 會需要一個 pre 去紀錄實際上最後一個使用到的 node 再將 pre.next 這個多餘的 node 刪掉
	在創造新的 cur.next = ListNode() 的地方 加上和進入下次迴圈相同的條件 就可以在最後一次迴圈時停止創造新的 node 於是我們有了 if (cur1 and cur2) or carry > 0 這個條件式 當 cur1 或 cur2 其一走到盡頭 只有在 carry > 0 時會追加 node 而 carry 最大為1，所以直接追加 cur.next = ListNode(1) 就不需要在跳出 while 後，還要再判斷一次 if carry > 0 去修正最後一個node的值

Code

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]:
    carry = 0
    head = cur = ListNode()
    cur1, cur2 = l1, l2
    while cur1 or cur2:
      if not cur1 or not cur2:
        remaining = cur2 if not cur1 else cur1

        while carry > 0:
          _sum = (remaining.val if remaining else 0) + carry
          cur.val, carry = _sum % 10, _sum // 10

          remaining = remaining.next if remaining else None

          if carry > 0:
            cur.next = ListNode(1)
            cur = cur.next
        
        if remaining:
          cur.next = remaining
          return head
        break
      
      _sum = cur1.val + cur2.val + carry
      cur.val, carry = _sum % 10, _sum // 10

      cur1, cur2 = cur1.next, cur2.next

      if (cur1 and cur2) or carry > 0:
        cur.next = ListNode(1)
        cur = cur.next

    return head

Last Updated on 2023/08/16 by A1go