[파이썬 알고리즘] 8장 - 두 수의 덧셈 (leetcode 2)

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

Add Two Numbers - LeetCode

<문제>

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.

 

<예시>

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] : Explanation: 342 + 465 = 807.
Input: l1 = [0], l2 = [0] Output: [0]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

 

---

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    head = cur = ListNode()
    carry = 0
    while l1 is not None or l2 is not None:
        # l1, l2의 길이가 동일하지 않은 경우 대비
        l1_value = 0 if l1 is None else l1.val
        l2_value = 0 if l2 is None else l2.val

        s = l1_value + l2_value + carry
        s, carry = s % 10, s // 10  # sum, carry 계산

        cur.next = ListNode(s) # 새 노드 생성하여 끝에 추가
        cur = cur.next

        l1 = l1 if l1 is None else l1.next
        l2 = l2 if l2 is None else l2.next

    if carry:
        # 만약 마지막 노드에서 carry 발생했다면 다음과 같이 추가
        cur.next = ListNode(carry)
    return head.next # 첫 노드는 dummy node

 

우리가 실제 덧셈하는 것을 떠올리면서 코드를 작성하면 매우 쉽게 풀 수 있는 문제였다.

(아랫자리부터 덧셈하고, 올림이 발생하는 것을 떠올리면 된다!)

 

이 중에 조금 주의해야 하는것은 l1, l2의 길이가 동일하지 않다는 점이다.

이 점을 유의해서 코드를 작성하면 된다