[자료구조] 링크드 리스트의 합 구하기

문제

Q. 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오.

예를 들어 아래와 같은 링크드 리스트를 입력받았다면,
각각 678, 354 이므로 두개의 총합
678 + 354 = 1032 를 반환해야 한다.

단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.

---

답

class Node:
    # 생성자
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    # 생성자
    def __init__(self, data):
        self.head = Node(data)

    # 추가
    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            return

        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = Node(data)

def get_linked_list_sum(linked_list_1, linked_list_2):
    # 구현해보세요!
    sum1 = get_sum(linked_list_1)
    sum2 = get_sum(linked_list_2)

    total = sum1 + sum2
    return total

def get_sum(linkedlist):
    sum = 0
    head = linkedlist.head
    while head is not None:
        # 자릿수에 맞춰 더하기
        sum = sum * 10 + head.data
        head = head.next
    return sum



linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)

print(get_linked_list_sum(linked_list_1, linked_list_2))

• 링크드 리스트는 배열처럼 직접 접근이 불가하다. 따라서 head를 활용해서 각 노드를 조회해야 한다.
• 중요한 부분은 덧셈을 할 때, 각 자리수에 맞춰서 덧셈을 하는것! 이었다.
  • 아 어려워
• 중복될 수 있는 부분은 함수로 따로 뺐다.

[출력]
1032