[Python] Leet Code 206. Reverse Linked List

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

자료형 변환

# 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, lst: ListNode) -> ListNode:

            node, prev = lst, 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

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> 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))

이 문제에서 배워야 할 포인트

• 변수 자료형 꼭 표시
• int(''.join(str(e) for e in a))
  • 숫자 -> 문자 -> 숫자 변형

전가산기 이용

# 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: ListNode, l2: ListNode) -> 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, val = divmod(sum + carry, 10)
  • 10으로 나눈 나머지는 값으로, 올림은 다음 루프로 넘김
• 입력과 결과를 어짜피 둘다 뒤집으므로, ListNode의 값 순서는 그대로