파이썬 알고리즘 인터뷰 16번 두 수의 합 (리트코드 2번)

Problem

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

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Solution

1차 풀이

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def set_node(self, l1, l2, current_node, extra_value=0):
        if l1 is None and l2 is None and extra_value == 0:
            return

        current_value = extra_value + getattr(l1, "val", 0) + getattr(l2, "val", 0)
        current_node.next = ListNode(val=current_value % 10)
        point = current_node.next

        self.set_node(getattr(l1, "next", None), getattr(l2, "next", None), point, current_value // 10)

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        answer = ListNode()
        self.set_node(l1, l2, answer)

        return answer.next

l1, l2 모두 일의 자리 수부터 표기가 되어 있고, 정답 역시 역순으로 표기하는 것이기 때문에 각 연결 리스트에서 하나씩 뽑으면서 더했다. 마지막에 모두 None이 되어도 extra value가 0보다 큰 경우도 발생하기에 extra_value == 0 인 케이스도 종료 조건에 포함시켰다.