1 minute read

2. Add Two Numbers

문제 링크

https://leetcode.com/problems/add-two-numbers/description/

문제 설명

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.

제한 사항

  • 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.

입출력 예 #1

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

입출력 예 #2

  1. Input: l1 = [0], l2 = [0]
  2. Output: [0]

입출력 예 #3

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

문제 풀이

  1. 연결 리스트를 파이썬 리스트로 변환하여 합을 구함
  2. 전가산기의 원리를 이용해 합을 구함
class Solution:
    # 연결 리스트 뒤집기
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node :
            next, node.next = node.next, prev
            prev, node = node, next

        return prev

    # 연결 리스트를 파이썬 리스트로 변환
    def toList(self, node: ListNode) -> ListNode:
        list: List = []

        while node:
            list.append(node.val)
            node = node.next
        
        return list

    # 파이썬 리스트를 연결 리스트로 변환
    def toReversedLinkedList(self, result: ListNode) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        
        return node

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))

        resultStr = str(int(''.join(str(e) for e in a)) + \
                        int(''.join(str(e) for e in b)))
        
        # 최종 계산 결과 연결 리스트 변환
        return self.toReversedLinkedList(resultStr)

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        root = head = ListNode(0)

        carry = 0
        while l1 or l2 or carry :
            sum = 0
            # 두 입력값의 합 계산
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            
            # 몫(자리올림수)과 나머지(값) 계산
            carry, val = divmod(sum + carry, 10)
            head.next = ListNode(val)
            head = head.next
        
        return root.next

Comments

You May Also Enjoy