문제 // 자료구조 // 리스트(List) // 뒤에서 K번째 노드구하기 // toJava

/**
 * [뒤에서 k번째 원소 구하기]
 *  단방향 연결리스트가 주어졌을 때 뒤에서 k 번째 원소를 찾는 알고리즘을 구현
 *
 * [풀이]
 *  => 전체길이를 캐싱하고 있는가 ?
 *  => 전체길이를 구하고 재차 뒤에서 K번째를 구함
 * */

public class Q02 {

    public static void main(String[] args) {

    }

    /* Node */
    static class Node {
        Node next;
        int data;
        Node(int data) {
            this.data = data;
        }
    }

    /* getNodeFromRear */
    static Node getNodeFromRear(Node head, int k) {
        if(head == null) return null;
        Node node = head;
        int count = 0;
        while(node.next != null) {
            node = node.next;
            count++;
        }

        node = head;
        int idx = 0;
        if(k <= count) {
            while(count - idx != k) {
                node = node.next;
                idx++;
            }
            return node;
        } else {
            return null;
        }
    }

    /* printNodeFromRear - 재귀 + 출력으로 해결하는 방법 */
    static int printNodeFromRear(Node head, int k) {
        if(head == null) return 0;
        int index = printNodeFromRear(head.next, k) + 1;
        if(index == k) {
            System.out.println(head.data);
        }
        return index;
    }

    /* getNodeFromRearB - Wrapper클래스 이용 */
    static class Index {
        public int value = 0;
    }
    static Node getNodeFromRearB(Node head, int k) {
        Index idx = new Index();
        return kthToLast(head, k, idx);
    }
    static Node kthToLast(Node head, int k, Index idx) {
        if(head == null) return null;
        Node node = kthToLast(head.next, k, idx);
        idx.value = idx.value + 1;
        if(idx.value == k) {
            return head;
        }
        return node;
    }

    /* getNodeFromRearC - static 이용 */
    static Node storage;
    static int getNodeFromRearC(Node head, int k) {
        if(head == null) return 0;
        int index = getNodeFromRearC(head.next, k) + 1;
        if(index == k) {
            storage = head;
        }
        return index;
    }

    /* getNodeFromRearD - 순환적방법 */
    static Node getNodeFromRearD(Node head, int k) {
        Node p1 = head;
        Node p2 = head;

        for(int i=0; i<k; i++) {
            if(p1 == null) return null;
            p1 = p1.next;
        }

        while(p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p2;
    }

}