링크드 리스트 끝에서 K 번째 값 출력하기

[문제]

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

[6] -> [7] -> [8] # 이러한 링크드 리스트가 입력되었을 때, 
                  # 끝에서 2번째 값은 7을 반환해야함

 

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이 나와야 합니다!

 

 

방법 1) 

한 바퀴 돌면서 링크드리스트의 길이를 알아낸 다음, 그

길이에서 k 만큼을 뺀 순서의 노드를 반환

    # 1. LinkedList 길이 전부 알아내기          시간복잡도: O(N)
    # 2. 그 길이에서 k 만큼 뺀 길이만큼 이동    시간복잡도: O(N-k)
    def get_kth_node_from_last(self, k):
        length = 1    # head 노드 포함
        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 만큼 뒤떨어진 포인터가 됨

# 1. 노드를 두 개 잡는다.
# 2. 한 노드를 다른 노드보다 k 만큼 떨어지게 한다.
# 3. 그리고 계속 한 칸씩 같이 이동한다.
# 4. 만약 더 빠른 노드가 끝에 도달했다면
#    느린 노드는 끝에서 k 만큼 떨어진 노드가 되므로
#    바로 반환하자.
# 빠른노드: O(N),        느린노드:O(N-k)
    def get_kth_node_from_last(self, k):
        slow = self.head
        fast = self.head

        for i in range(k):
            fast = fast.next
        while fast is not None:
            fast = fast.next
            slow = slow.next
        return slow

 

 

 

[내가 만든 코드]

    def get_kth_node_from_last(self, k):
        node_array = []
        current_node = self.head
        node_array.append(current_node)
        while current_node.next is not None:
            current_node = current_node.next
            node_array.append(current_node)
        array_len = len(node_array)
        print(node_array)
        return node_array[array_len - k]

 

반복문을 두 번 도는 것보다 한 번 도는 게 무조건 빠르다고는 생각 안하셨으면 좋겠습니다

 

 

방법 1)과 방법 2)의 시간복잡도는 동일함. 방법 2)에서 방법 1)보다 개선된건 없음 코드 길이만 줄었을 뿐
시간 복잡도를 분석하기 위해서는 코드에서 실행된 연산량을 통해 추정하는 게 더 올바른 생각의 흐름이다