1. 문제

• [5] -> [6] -> [7]과 같은 linked list가 있다. 본 linked list의 끝에서 k번째 노드(node)를 반환해보자

2. 나의 전략

① 전략

• linked list의 끝으로 이동해서 마지막 노드(node)를 맨 앞(head)으로 이동시키고, 기존 마지막 노드(node)는 삭제한다.

② 성공 여부

• 코드로 구현하지 못했다.
• 마지막 노드(node)를 삭제하지 못하여 중간에 있는 숫자를 가장 앞으로 옮겨오지 못했다.
• 이렇게 만들면 원래 linked list 형태가 사라져 재사용이 불가능하다.
• 너무 어렵게 생각했다. index 부여하면 바로 찾을 수 있을걸...

③ 코드

• 아래 코드는 실패한 코드이다.

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

        count = 0
        cur = self.head
        while cur.next is not None:
            cur = cur.next
 		
        self.head = cur
        
        # 삭제는 어쩌지?
        while cur.next is not None:
            cur = cur.next
        ....

        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)

3. 다른 방법

① 전략

• cur을 linked list 끝까지 이동하며 index를 기록한다. 접근하고자 하는 노드의 순서만큼 linked list에서 다시 이동해 원하는 데이터에 접근한다.

② 성공 여부

• 성공
• 가장 처음 생각한 것보다 더욱 이해하기 쉽고, 코드 작성도 용이하다.

③ 코드

- 슈도 코드

# 1. index 변수를 1로 선언한다.
# 2. 돌아다닐 cur 변수를 선언한다.

# 3. linked list 끝까지 이동하며 index + 1한다.

# 4. 찾고자 하는 index를 설정한다.
# 5. 다시 linked list를 index만큼 움직여 원하는 데이터에 접근한다.
# 6. 결과를 반환한다.

- 코드

    def get_kth_node_from_last(self, k):

        index = 1                     	 # 1. index 변수를 1로 선언한다. 
        cur = self.head		     	 # 2. 돌아다닐 cur 변수를 선언한다.
        while cur.next is not None: 	 # 3. linked list 끝까지 이동하며 index + 1한다.
            cur = cur.next
            index += 1

        kth_node_index = index - k       # 4. 찾고자 하는 index를 설정한다.
        cur = self.head

        for i in range(kth_node_index):  # 5. 다시 linked list를 index만큼 움직여 원하는 데이터에 접근한다.
            cur = cur.next

        return cur			 # 6. 결과를 반환한다.

4. 배운 점

① 어렵게 생각하는 경향

• 특정 문제를 해결하는 방법은 다양하다. 나는 문제를 조금 어렵게 생각하는 경향이 있다. 그래서, 문제를 풀기 위해 많은 기법과 노력이 필요하다. 이 점은 고쳐야 한다. 가장 효율적, 효과적인 방법이 가장 좋은 문제 해결 방법이라고 생각하기 때문이다.
• 쉬운 전략을 짜기 위해서는 어떻게 해야할까? 최소한의 변화로 정답을 이끌어내야 한다는 점을 기억하자. 본 문제에서는 linked list가 변하고고, data를 찾는 수고로움에도 강행하니 시간이 오래걸리지 않았는가. 어쩌면 정답은 자연과 같이 심플한 형태를 갖추고 있을 것이라고 생각하자.

② linked list 접근 방법

• 실패했지만, 배운 점도 있다.
• linked list에 접근하고 연결 원리에 대해 조금 더 익숙해졌다. 연결고리로 각 노드를 연결하고, 해체하는 방법이 머릿속에 조금 더 각인되었다.