문제

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

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

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

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

풀이

내 풀이

두 연결 리스트의 길이를 맞추기 위해서 값이 0인 연결리스트를 추가 해줘서 길이를 맞추어
두 수를 덧셈 해줌 -> 150 ms

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        l1_trav, l2_trav = l1, l2
        l1_prev = None
        next_val = 0
        while l1_trav.next or l2_trav.next:

            if not l1_trav.next:
                l1_trav.next = ListNode(0)
            if not l2_trav.next:
                l2_trav.next = ListNode(0)
                
            l1_trav.val, next_val = (l1_trav.val + l2_trav.val+ next_val) % 10 , (l1_trav.val + l2_trav.val + next_val) // 10
            

            l1_trav, l2_trav = l1_trav.next, l2_trav.next
            
        l1_trav.val, next_val = (l1_trav.val + l2_trav.val+ next_val) % 10 , (l1_trav.val + l2_trav.val + next_val) // 10
        
        if next_val:
            l1_trav.next = ListNode(next_val)

        return l1

책 풀이

자료형 변환

연결 리스트를 문자열로 이어 붙인다음 숫자로 변환하고, 이를 모두 계산한 후 다시 연결리스트로 바꾼다.
-> 비효율적 풀이 : 160 ms

class Solution:
    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))


    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) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next

        return list

    def toReversedLinkedList(self, result: str) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node

        return node

전가산기 구현

내가 한 방법이랑 비슷함
더 나은 부분은
1. 몫과 나머지 계산을 divmod()로 계산
2. l1에 값을 더한게 아니라 새로운 리스트 노드를 만들어서 값을 반환
->129 ms

    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