2. Add Two Numbers (Linked List, Math, Recursion)

링크 - https://leetcode.com/problems/add-two-numbers/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

단순 덧셈 문제이다. carry를 꼭 사용해야한다는 것을 잊지말자.

Code

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        dummy = ListNode(-1)
        node = dummy

        while l1 or l2 or carry > 0:
            cur_val = carry
            if l1:
                cur_val += l1.val
                l1 = l1.next
            if l2:
                cur_val += l2.val
                l2 = l2.next
            
            node.next = ListNode(cur_val % 10)
            node = node.next
            carry = cur_val // 10

        return dummy.next

Complexity

Time Complexity: O(max(m, n)

Space Complexity: O(1)