뒤에서 k번째 노드 값(data) 출력하기

노드의 맨 끝까지 돌아 노드의 길이를 알아낸 후 노드의 길이에서 뒤에서 몇 번째 노드를 출력해야하는 지 그 값(k값)을 빼서 노드의 인덱스를 찾아 for문을 인덱스 번호만큼 돌리면서 노드를 이동해 준 후 그 노드의 값을 출력해준다.

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):
        length = 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


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

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

길이를 찾을 때 head값도 길이에 포함시켜야 하므로 length의 초기 값을 0이 아닌 1로 설정하였고, cur의 다음 값이 있을 때만 cur을 다음으로 이동하고 길이를 더해주어야 하므로 while문의 조건을 cur is not None이 아닌 cur.next is not None으로 하였다.

노드의 값이 6 -> 7 -> 8 이런식으로 담겨 있는데 cur is not None을 조건으로 설정해준다면 현재 노드의 값이 8일 때도 while문 안으로 들어가 노드를 다음으로 옮기고 길이도 1을 더해주어 길이가 1만큼 더 길게 나올 것이다. 

따라서 다음 노드의 값이 none이 아닌 7일 때 까지만 while문 안에 들어가 노드를 다음으로 옮겨주고 길이를 1을 더해준다. 그러면 노드의 값이 6일 때 길이는 1이고, 7일 때 2, 8일 때 3으로 길이가 1씩 증가한 후 while문을 탈출하게 된다. 그 후, 뒤에서 k번 째 노드이므로 구한 전체의 길이에 k값을 빼 end_length라는 변수에 저장해 놓고, for문을 end_length만큼 돌려서 노드를 반환한 후 노드의 값을 출력해주면 뒤에서 k번째 노드의 값을 출력할 수 있다.