[Leetcode/파이썬] 2. Add Two Numbers

Add Two Numbers

---

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.

 

Example 1:

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

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

# 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]:
        dummy = ListNode(0)
        res = dummy

        sm = flag = 0

        while l1 or l2 or flag :
            sm = flag

            if l1 :
                sm += l1.val
                l1 = l1.next
            if l2 :
                sm += l2.val
                l2 = l2.next

            num = sm % 10
            flag = sm // 10

            dummy.next = ListNode(num)
            dummy = dummy.next

        return res.next

흔히 우리가 하는 덧셈과는 조금 다른 덧셈이다. 덧셈의 결과가 10 이상이면 앞자리로 보내는게 아니라 뒷자리로 보내는 아주 신기한 덧셈 방법이다. 링크드리스트로 표현하라. 

next 표현하는데 좀 어려움이 있었다. ListNode를 추가하면서 표시해야되는구나. 초기 설정으로

• dummy : 더미 노드
• res : 최종 결과 링크드리스트
• sm : 합산 결과를 담을 변수
• flag : 합산이 10 넘어갈 경우 여기에 10 이상 숫자를 담을 변수

while 문은 좀 어려웠다. 처음에는 l1과 l2의 자리수를 같게 하려고 l1이 더 기냐 l2가 더 기냐 한 다음 짧은 변수에 0을 추가하는 방식을 썼는데 비효율적이고 문제 해결에 큰 도움이 되지 않았다. 그러나 간단한 방법으로 문제가 해결되었다. 

l1이 있냐, l2가 있냐, flag가 0이 아니냐 를 저런 식으로 표현이 가능했다. 이후 현재값 기준으로 합산 sm의 초기값을 flag로 초기화, l1, l2 의 현재값을 더한다. 그리고 포인터를 다음으로 이동. 만약 없으면 건너뛰게 된다. 

num, flag는 10 미만, 10 이상의 값을 각각 담는 변수이며 dummy 의 현재 노드에는 num을, 포인터를 next로 옮긴다. 이를 반복.