본문 바로가기
IT/알고리즘

[Medium] 두 숫자 더하기

by 네야나라 2024. 4. 3.
반응형

문제:

 

두 개의 비어 있지 않은 연결 리스트가 주어지며, 이들은 두 개의 음이 아닌 정수를 나타냅니다. 숫자들은 역순으로 저장되

어 있으며, 각 노드는 하나의 숫자를 포함합니다. 두 숫자를 더하고 그 합을 연결 리스트로 반환하세요.

 

두 리스트의 숫자는 0인 경우를 제외하고 0으로 시작하지 않습니다.

 

예시1:

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

 

예시2:

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

 

예시3:

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

 

제약 조건:

각 연결 리스트의 노드 수는 [1, 100] 범위에 있습니다.

0 <= 노드 값 <= 9

리스트의 시작이 0이 아니라는 것이 보장됩니다.

 

 

정답:

# 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]:
        dummyHead = ListNode(0)
        tail = dummyHead
        carry = 0

        while l1 is not None or l2 is not None or carry != 0:
            digit1 = l1.val if l1 is not None else 0
            digit2 = l2.val if l2 is not None else 0

            sum = digit1 + digit2 + carry
            digit = sum % 10
            carry = sum // 10

            newNode = ListNode(digit)
            tail.next = newNode
            tail = tail.next

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

        result = dummyHead.next
        dummyHead.next = None
        return result
반응형