3.6

main.py

"""
문제 3.6. 주어진 2개의 연결리스트로 표현되는 양의 정수의 합의 결과를 연결리스트로 반환을 해보자.
예를 들어서, 1 -> 2 -> 3과 4 -> 5 -> 6이 주어졌다면, 5 -> 7 -> 9를 반환 하면 된다.

## 제한 사항

1. 연결리스트는 양의 정수로 표현
2. 1번째 노드는 가장 높은 자리의 숫자
3. 주어진 두 연결 리스트는 무조건 값이 있다.
4. 0을 제외하고 0으로 시작하는 숫자는 없다. (0 -> 3 -> 3 과 같은 입력은 없다.)

아이디어 (스택)
1. 스택 2개를 생성한다.
2. 각 연결리스트 (l1, l2)를 각각 순회하면서 노드 값을 스택에 넣어주.
3. 스택의 값을 하나씩 꺼내서 자리수를 더해 나가도록 하자. 더해진 각 값을 새로운 연결 리스트의 노드로 연결을 해주자.

아이디어 (연결 리스트 뒤집기)

1. 2개의 연결 리스트를 뒤집는다.
2. 뒤집은 연결리스트로 순회하여 각 자리수를 더한다. 각 자리 숫자를 더하면서 새로운 노드를 생성하고 연결한다.

아이디어 (문자열 연산)

1. 각 연결 리스트를 순회하면서 문자열로 전환하고 문자열에 숫자를 추가한다.
2. 두 문자열을 int()로 변환한다.
3. 정수를 다시 str()로 변환한다.
4. 각 자리를 접근하면서 연결 리스트를 구성한다.

"""


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


def addTwoNumbers(l1: Node, l2: Node) -> Node:
    st1 = []
    st2 = []

    l1_curr = l1
    l2_curr = l2

    head = None

    while l1_curr != None:
        st1.append(l1_curr.val)
        l1.curr = l1_curr.next

    while l2_curr != None:
        st2.append(l2_curr.val)
        l2.curr = l2_curr.next

    carry = 0

    while st1 or st2:
        num1 = st1.pop() if st1 else 0
        num2 = st2.pop() if st2 else 0

        carry, num = divmod(num1 + num2 + carry, 10)

        node = Node(num)

        if head == None:
            head = node
        else:
            temp = head
            head = node
            node.next = temp

    if carry != 0:
        node = Node(carry)
        temp = head
        head = node
        node.next = temp

    return head


def addTwoNumbers2(l1: Node, l2: Node) -> Node:
    def reverse(head):
        prev = None
        curr = head

        while curr != None:
            next_temp = curr.next
            curr.next = prev

            prev = curr
            curr = next_temp

            prev = curr
            curr = next_temp
        return prev

    r_l1 = reverse(l1)
    r_l2 = reverse(l2)

    res_head = None

    carry = 0

    while r_l1 != None or r_l2 != None:
        num1 = 0
        num2 = 0

        if r_l1 != None:
            num1 + r_l1.val
            r_l1 = r_l1.next

        if r_l2 != None:
            num2 = r_l2.val
            r_l2 = r_l2.next

        carry, num = divmod(num1 + num2 + carry, 10)

        node = Node(num)
        if res_head == None:
            res_head = node
        else:
            temp = res_head
            res_head = node
            node.next = temp

        if carry != 0:
            node = Node(carry)
            temp = res_head
            res_head = node
            node.next = temp

        return res_head


def addTwoNumbers3(l1: Node, l2: Node) -> Node:
    num1_str = ""
    num2_str = ""

    l1_curr = l1
    l2_curr = l2

    while l1_curr != None:
        num1_str = num1_str + str(l1_curr.val)
        l1_curr = l1_curr.next

    while l2_curr != None:
        num2_str = num2_str + str(l2_curr.val)
        l2_curr = l2_curr.next
    
    res_num = int(num1_str) + int(num2_str)
    
    head = Node(-1)
    curr = head
    for num_ch in str(res_num):
        curr.next = Node(int(num_ch))
        curr = curr.next

    curr.next = None
    return head.next