[알고리즘] - 링크드 리스트 끝에서 K 번째 값 출력하기/파이썬

문제

Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오.

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_kth_node_from_last(self, k):
        # 구현해보세요!
        return self.head

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

print(linked_list.get_kth_node_from_last(2).data)  # 7이 나와야 합니다!

정답 풀이

우선, 링크드 리스트의 특징을 떠올려 보자.

링크드 리스트는 next 만 알고 있어서 다시 돌아가지 못한다. 그래서 어디가 끝인지 몰라 뒤에서 k 번째 노드를 찾기 쉽지 않다.

그렇다면, 길이를 알아낸 다음, 그 길이에서 k 만큼을 뺀 순서의 노드를 반환하면 된다.

def get_kth_node_from_last(self, k):
        length = 1  # 시작 노드의 길이를 세기 위해 1부터 시작합니다
        cur = self.head

        while cur.next is not None:
            cur = cur.next
            length += 1
        end_length = length - k
        cur = self.head
        for i in range(end_length):
            cur = cur.next
        return cur

위 코드보다 조금 더 개선된 코드를 작성할 수 있다. 바로 2개의 포인터를 사용하면 된다.

k만큼의 길이가 떨어진 포인터를 두개를 두고, 한 칸씩 이동하면 어떨까? 언젠가 앞에 나선 포인터가 끝에 도달하게 된다.

그 때 k 만큼 뒤떨어져있던 포인터는, 바로 끝에서부터 k 만큼 뒤떨어진 포인터가 된다.