박종훈 알고리즘 블로그

리스트의 합

리스트의 합: 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.

입력 : (7→1→6) + (5→9→2), 즉 617 + 295
출력 : 2→1→9, 즉 912

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

def sum_of_two_linked_list(a, b):
    number_a = linked_list_to_number(a)
    number_b = linked_list_to_number(b)
    return (number_to_linked_list(number_a + number_b))

def linked_list_to_number(node):
    result = 0
    digit = 1

    pointer = node
    while(True):
        result += pointer.val * digit
        if (pointer.next != None):
            pointer = pointer.next 
            digit = digit * 10
        else:
            break
    return result

def number_to_linked_list(number):
    char_list = list(str(number))
    head = Node(char_list[-1])
    del char_list[-1]

    pointer = head
    for char in reversed(char_list):
        node = Node(char)
        pointer.next = node
        pointer = node
    return head

linked_list_a = Node(7, Node(1, Node(6)))
linked_list_b = Node(5, Node(9, Node(2)))

result = sum_of_two_linked_list(linked_list_a, linked_list_b)
while result:
    print(result.val, end = "")
    if result.next:
        result = result.next
        print(" -> ", end="")
    else:
        result = None

array reverse 와 reversed 함수의 차이

for char in reversed(char_list): 이 부분에서 reversed 를 쓴 이유에 대한 설명이다.

두 함수 모두 리스트의 순서를 뒤집는다는 점에서 비슷하지만 아래와 같은 차이가 있다.
array reverse 함수는 원본 객체를 뒤집습니다. 뒤집은 후 반환값은 없습니다. (Void)
reversed 한수는 원본 객체를 변경하지 않고 새로운 iterator를 생성합니다.