leetcode-LL

445. Add Two Numbers II.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    Solution: using stack -> O(n) in space
    
        we use stack to simulate addition.
        because when we traverse the array, the last visited node is going te be used first.

        Last in, First out -> stack
    
    Aks for doing this in O(1) in terms of space
        -reversed two linked list
        -then follow add two numbers
    
    Aks for you cannt modify the input lists.
        
    """
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def get_stack(ll):
            cur = ll
            stack = collections.deque([])
            while cur:
                stack.append(cur.val)
                cur = cur.next
            return stack
        
        l1_stack = get_stack(l1)
        l2_stack = get_stack(l2)
        carry = 0
        d = ListNode(-1)
        cur = d
        while l1_stack or l2_stack or carry:
            if l1_stack:
                v1 = l1_stack.pop()
            else:
                v1 = 0
            if l2_stack:
                v2 = l2_stack.pop()
            else:
                v2 = 0
            
            carry, remainder = divmod(v1+v2+carry, 10)
            # 這邊要注意處理產生linked list的順序
            new_node = ListNode(remainder)
            new_node.next = cur.next
            cur.next = new_node
        return d.next
    
    def get_reversed(self, head):
        d = ListNode(-1)
        d.next = head
        cur = head.next
        head.next = None
        while cur:
            nxt = cur.next
            cur.next = d.next
            d.next = cur
            cur = nxt
        return d.next