[LeedCode] 2. Add Two Numbers 파이썬 Medium

문제 해석:

두개의 링크드 리스트가 주어진다. 
각 한자리 숫자가 연결되어 있다. 
각 링크드 리스트에 연결되어있는 숫자로 거꾸로 뒤집어 꺼낸다. 
이후, 두 숫자를 합하여 링크드리스트에 다시 뒤집어 넣어 리턴한다.

문제 해설:

( 처음에는 숫자를 꺼내서 뒤집고 계산한 다음에 다시 거꾸로 넣어줬다.. BTW 더 좋은 방법이 아래 있다. )

1. 링크드 리스트에서 순서대로 한자리 숫자를 더하고, 나머지를 저장한다
2. 1번과 마찬가지로 숫자를 더하고, 10으로 나눈 몫을 저장한다.
3. 1번에서 구한숫자는 정답으로 리턴할 리스트에 넣는다.
4. 2번에서 구한 10의 자리 숫자는 다음 숫자를 합할때 포함시킨다.
5. 숫자 두개를 더 했을때 두자리 숫자가 나오는것을 나누기와 모듈러 연산으로 나눠서 다음 계산때 넣어주고 다시 리스트에 넣어주면 여러번 뒤집고, 꺼내고, 넣는 일을 반복할 필요가 없다.

 

2. 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]:
    	# 정답으로 저장할 리스트, 정답에 넣을 위치를 표시하는 curr
        ans = curr = ListNode()
        carry = 0
        while l1 or l2:
        	# 값이 아예 존재하지 않으면 0을 더해주면 된다.
            if not l1:
                l1 = ListNode(0)
            if not l2:
                l2 = ListNode(0)
            # 리스트의 각각의 값을 더한다 + 이전 계산에서 올라온 10의 자리도 마찬가지
            addValue = (l1.val + l2.val + carry) % 10
            # 현재 위치에서 더한 값들이 두 자리수가 되면 올릴 숫자 
            carry = (l1.val + l2.val + carry) // 10
            curr.next = ListNode(addValue)
            l1 = l1.next
            l2 = l2.next
            curr = curr.next
        # 만약 두 리스트의 마지막 숫자들을 합했을때 올릴 숫자가 존재하면 리스트에 넣아줘야한다.
        if carry > 0:
            curr.next = ListNode(carry)
        # 리스트를 처음 아무것도 없이 생성했기때문에 .next로 반환
        return ans.next