[알고리즘][연결 리스트] - 4. 두 수의 덧셈

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/add-two-numbers/submissions/

역순으로 저장된 연결 리스트의 숫자를 더하라.

---

[자료형 반환]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
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 : str) -> ListNode:
        prev: ListNode = None
        for i in result:
            node = ListNode(i)
            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 = int(''.join(str(e) for e in a)) + int(''.join(str(e) for e in b))
        
        return self.toReversedLinkedList(str(resultStr))

• 연결 리스트를 뒤집어 준다.
• 연결 리스트를 파이썬 리스트로 변환해준다.
• 파이썬 리스트를 다시 연결 리스트로 변환한다.
• 두 연결 리스트의 덧셈을 해준 뒤 최종적으로 결과 연결 리스트를 반환해준다.

 

 

[전가산기 구현]

# 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]:
        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

• 두 입력값의 합을 먼저 구해준다.
• 자릿수가 넘어갈 경우에는 자리 올림수를 결정해 줄 것인데 이를 carry, value = divmod(sum + carry, 10)으로 (a//b, a%b)의 결과를 받아 올림 수가 있으면 다음 합에 영향을 줄 수 있게 구현 한다.