[Python] LinkedList 예제 - 두 링크드 리스트의 합

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

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

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

 

접근 방법

1. get_num() 함수를 통해 링크드리스트를 숫자로 변환한다 (ex. [6]-[7]-[8] → 678)

2. 이를 위해 get_len() 함수를 통해 전체 링크드리스트의 길이를 구한다

3. get_node() 함수를 통해 각 인덱스 위치의 데이터 값을 구한다

4. 2에서 구한 길이를 통해 맨 마지막 위치의 index를 파악하고, 여기서부터 역순으로 링크드리스트의 자릿수와 3의 데이터값을 곱해 더한다

 

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


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def get_node(self, index):
        cur = self.head
        cur_index = 0

        while cur_index != index:
            cur = cur.next
            cur_index += 1

        return cur

    def get_len(self):
        cur = self.head
        cur_index = 0

        while cur is not None:
            cur = cur.next
            cur_index += 1

        return cur_index

    def get_num(self):
        cur_index = self.get_len() - 1
        square_num = 1
        num = 0

        while cur_index != -1:
            num += self.get_node(cur_index).data * square_num
            square_num *= 10
            cur_index -= 1
        return num

def get_linked_list_sum(linked_list_1, linked_list_2):

    ll_1_num = linked_list_1.get_num()
    ll_2_num = linked_list_2.get_num()

    return ll_1_num + ll_2_num

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))