본문 바로가기

기록

LeetCode 0002. Add Two Numbers(Python)

문제

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 0819. Most Common Word(Python)  (0) 2021.05.24
LeetCode 0344. Reverse String(Python)  (0) 2021.02.25
LeetCode 0001. Two Sum  (0) 2021.01.21
Windows Terminal 테마와 폰트 수정하기  (0) 2020.05.29
Pyenv로 파이썬 버전 관리하기  (0) 2020.02.23