[리트코드] 2. Add Two Numbers

# 문제 설명

역순으로 단일 10진수 (0~9)값을 저장하는 연결리스트 2개가 주어진다. 2개의 수를 합친 값을 연결리스트로 반환해라.

단, 주어진 연결리스트는 비어있지 않고, 음수 값을 저장하지 않는다.

 

# 입출력 예시

입력	출력
2 -> 4 -> 3 5 -> 6 -> 4	7 -> 0 -> 8
0 0	0
9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 9 -> 9 -> 9 -> 9	8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1

첫번째 입력을 설명하자면, 각각의 연결리스트를 역순으로 한 342 + 465 을 계산하면, 807 이 된다.

 

 

# 코드 풀이 1. 재귀를 사용한 풀이

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        sum = (l1 and l1.val or 0) + (l2 and l2.val or 0) # 현재노드 합
        carry, val = divmod(sum) # 캐리, 값 계산
        
        if not l1.next and not l2.next and not carry: # 끝남
            return sl
        elif not l1.next and not l2.next and carry:
            l1.next = ListNode(carry)
            l2.next = ListNode(0)
        elif not l1.next:
            l1.next = ListNode(carry)
        elif not l2.next:
            l2.next = ListNode(carry)
        else: # if carry > 0:
            l1.next.val += carry
        
        sl = ListNode(val)
        sl.next = self.addTwoNumbers(l1.next, l2.next)  # 순방향
        return sl

 

# 코드 풀이 2. 반복을 사용한 풀이

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        root = head = ListNode() # 맨처음 노드, 연산수행 노드
        
        carry = 0 # 올림수
        while l1 or l2 or carry: # 3중 하나라도 있다면
            sum = 0 # 합 계산
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            
            # 몫(올림수), 나머지(값) 계산
            carry, val = divmod(sum + carry, 10)
            head.next = ListNode(val) # 현재노드 설정
            head = head.next
        return root.next

 

# 핵심 포인트

• 순서대로 값을 반환하기 위해 맨처음 노드 변수를 두거나, 재귀로 다음 노드를 계산해서 연결할 수 있다.
• 몫과 나머지를 계산하기 위해 divmod() 함수를 사용한다.