2.2 뒤에서 k번째 원소 구하기

문제 

단방향 연결리스트가 주어졌을때 뒤에서 k번째 원소를 찾는 알고리즘을 구하여라

 

해법 1 연결리스트의 길이를 아는경우 -> 길이 - k번째 원소 찾기 

 

해법 2 재귀적으로 해결하기 

마지막 원소를 만나면 0으로 설정된 카운터 값을 반환하고, 재귀적으로 호출된 부모 매서드는 그값에 1을 더한다. 

카운터 값이 k가 되는 순간 뒤에서 K번째 원소에 도달한 것이다.

하지만 문제가 있다. 대부분의 언어에서는 노드와 카운트 값을 동시에 반환할 수 없다.

 - 1. 반환하는 것이아니라 출력한다고 가정하면 k번째에 도달한 순간 출력하면된다.

 - 2. call by reference를 이용하여 문제를 해결한다.

node* nthToLast(node* head, int k , int& i ){
    if(head == NULL) return NULL;
    node* nd= nthToLast(head->next, k, i)
    i = i+1
    if (i == k) return head;
    return nd;
}

 

해법 3 순환적으로 해결하기

 Runner 기법을 이용하여, 두개의 pointer를 하나는 k노드만큼 움직여서 p1과 p2가 k만큼 떨어져있도록 설정한 후에 p1(앞에 있는 포인터)가 리스트의 끝을 만났을때 p2가 위치한 노드가 뒤에서 k만큼 떨어진 원소가 될 것이다.

def Solution(node,k):
    p1 = node
    p2 = node
    for _ in range(k):
        p1 = p1.next

    while p1 is not None:
        p1 = p1.next
        p2 = p2.next

    return p2