알고리즘 오답노트 03

링크드 리스트 뒤에서 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):
    # 1번 방법
    # cur = self.head
    # count = 1
    # while cur.next is not None:
    #   cur = cur.next
    #   count += 1
    # while count - k > 0:
    #   cur = self.head.next
    #   count -= 1
    # return cur
    
    # 2번 방법
    # 앞에서 k번째 떨어진 노드를 찾고 k만큼의 거리를 유지하며 위치가 0과 k인 두 노드를 k가 끝에 다다를때까지 함께 움직인다. 그러면 앞쪽에 있는 노드가 뒤에서 k번째 노드가 된다. 와우.... 하지만 두 방법 모두 링크드 리스트 끝까지 가야하므로 O(N) 이다.
    fast = self.head
    slow = 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_kth_node_from_last(2).data)  # 7이 나와야 합니다!