[Python] LinkedList 예제 - 끝에서 K 번째 값 출력하기

문제

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

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

 

접근 방법 1

1. 전체 Linked List의 길이를 구하는 함수 get_len() 함수 구현

2. 특정 인덱스의 노드를 찾는 함수 get_node() 함수 구현

3. 1의 함수를 이용해 구한 Linked List의 전체 길이에서 K를 빼면 찾고자 하는 노드의 인덱스가 됨

4. 2의 함수를 이용해 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_len(self):
        linked_list_len = 1
        cur = self.head

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

        return linked_list_len

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

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

        return cur

    def get_kth_node_from_last(self, k):
        linked_list_len = self.get_len()
        kth_node_index = linked_list_len - k

        return self.get_node(kth_node_index)


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

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

 

접근 방법 2

1. K만큼 간격을 둔 slow 노드와 fast 노드를 두고, 두 노드를 동시에 이동시킴

2. fast 노드가 Linked List의 맨 마지막 노드에 도착했을 때, slow 노드는 자연스럽게 맨 끝에서 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)

        return cur

    # slow, fast 노드를 두고 이동시키기
    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:
            slow = slow.next
            fast = fast.next

        return slow


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

print(linked_list.get_len())

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

 

시간 복잡도

코드 상에서는 방법 2가 훨씬 간단하다. 그러나 두 방법 모두 결국 Linked List의 끝까지 모든 노드를 확인해야 하기 때문에 시간 복잡도는 동일하게 O(n)이다. 

 

참고 강의

https://www.inflearn.com/course/38%EA%B5%B0%EB%8D%B0-%ED%95%A9%EA%B2%A9%EB%B9%84%EB%B2%95-%EC%BD%94%ED%85%8C-%ED%95%84%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard

38군데 합격 비법, 2024 코딩테스트 필수 알고리즘 강의 | 딩코딩코 - 인프런