445. Add Two Numbers II

Loading...LeetCode

参考 Q2，用 decode - encode 的方式写，不做逆序。

2. Add Two Numbers

12/30/2020 Update:

把两个左对称的 linked list 变成右对称 ----> 可以用 stack，last in first out

两个 stack 加起来变回 linked list 的方法也不简单，注意 residual 和对 next 指针的处理。

decode (no reverse)

# 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:
        return self.encode(self.decode(l1) + self.decode(l2))
    
    def decode(self, node):
        number = 0
        while node:
            number *= 10
            number += node.val
            node = node.next
        return number
            
    def encode(self, number):
        tail = None
        if number == 0: return ListNode(0)
        while number:
            number, m = divmod(number, 10)
            cur = ListNode(m)
            cur.next = tail
            tail = cur
        return tail

stack

# 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:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        
        residual = 0
        prev = None
        
        while s1 or s2 or residual:
            n1 = s1.pop() if s1 else 0
            n2 = s2.pop() if s2 else 0
            number = n1 + n2 + residual
            residual, number = divmod(number, 10)
            curr = ListNode(number)
            curr.next = prev
            prev = curr
            
        return prev