[LeetCode] 2. Add Two Numbers

문제 링크 : leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

이 문제는 두 linked list의 값들을 역순으로 하여 더한 결과의 역순을 linked list로 반환하는 문제이다.

 

풀이방법

두 linked list와 반환해야 할 linked list사이의 규칙을 찾아보면 역순으로 연결되어 있기 때문에 linked list의 시작이 가장 낮은 자릿수인 것을 알 수 있다. 따라서 두 linked list를 동시에 탐색하면서 값을 더하여 새로운 linked list를 만들면 되는 것이다.

sum_list.val = (l1.val + l2.val)
sum_list = sum_list.next

다만 여기서 주의해야 할 점은 l1.val + l2.val 의 값이 10을 넘었을 경우이다. 10을 넘었을 경우에는 다음 list에 값을 넘겨주어야 하므로 l1.val + l2.val 의 몫과 나머지를 따로 계산하여 몫은 다음 list로, 나머지는 value로 사용하면 된다.

remain_value = (l1.val + l2.val) // 10
sum_list = (l1.val + l2.val) % 10 # divmod 함수도 사용 가능
sum_list = sum_list.next
sum_list.val = remain_value

그리고 l1, l2의 조건에 맞게 코드를 정리하면 된다.

"""

# 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: ListNode, l2: ListNode) -> ListNode:
        sum_list = ListNode()
        curr = sum_list
        while l1 or l2:
            if not l1:
                remain_val = (curr.val + l2.val) // 10
                curr.val = (curr.val + l2.val) % 10
                l2 = l2.next
            elif not l2:
                remain_val = (curr.val + l1.val) // 10
                curr.val = (curr.val + l1.val) % 10
                l1 = l1.next
            else:
                remain_val = (curr.val + l1.val + l2.val) // 10
                curr.val = (curr.val + l1.val + l2.val) % 10
                l1 = l1.next
                l2 = l2.next
            if l1 or l2:
                curr.next = ListNode()
                curr = curr.next
                curr.val = remain_val
        # 마지막 자릿수 확인
        if remain_val == 1:
                curr.next = ListNode()
                curr = curr.next
                curr.val = remain_val
        return sum_list

다른 사람들의 코드를 보니 l1, l2가 동시에 존재할 때 먼저 while문을 돌리고, 그 다음 l1, l2 순서로 while문을 돌리는 쪽이 조금 더 가독성이 좋았다.