본문 바로가기

개발/알고리즘

LeetCode 0002. 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.

해결방법

Linked List 형태로 입력되는 두 수의 합을 구하여 Linked List 형태로 반환하는 문제. 때문에 입력되는 두 수는 모두 일반적인 숫자 순서를 뒤집어진 상태로 들어온다. 첫 번째 아이템끼리 더하고 두 번째 아이템끼리 더하는 식이다. 뭐 따로 설명할 건 없고 올림수 처리만 잘 하면 될 것 같다. result에 더미를 만들기 싫었는데 다른 방법을 생각해내지 못해 더미를 만들어 사용했다.

테스트 코드도 계속 작성하려고 하다 보니 LeetCode 상 예시의 숫자 배열을 ListNode로 바꿔주는 코드를 작성하였고, ListNode 객체들의 비교를 위해 __eq__ 함수를 정의하여 작성하였다.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __eq__(self, other):
        while self and other and self.val == other.val:
            print(self.val == other.val)
            self = self.next
            other = other.next
        if not self and not other:
            return True
        return False


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = ListNode(0)
        current = result
        carry = 0
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            sum = x + y + carry

            carry = sum // 10
            rest = sum % 10

            current.next = ListNode(rest)
            current = current.next

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

        if carry:
            current.next = ListNode(carry)

        return result.next

GitHub

'개발 > 알고리즘' 카테고리의 다른 글

LeetCode 0002. Add Two Numbers  (0) 2021.01.22
LeetCode 0001. Two Sum  (0) 2021.01.21