// D. Scott
// CCI - Problem 2.2
// Return the value of the kth node from the end of a singly linked list

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}


public static void main (String[] args)
{
    // generate list
    Node list = new Node(19);
    Node head = list;
    list.appendToTail(5);
    list.appendToTail(8);
    list.appendToTail(143);
    list.appendToTail(2);
    list.appendToTail(12);
    list.appendToTail(36);
    list.appendToTail(14);
    list.appendToTail(99);
    list.appendToTail(7);

    // compute total number of nodes in list
    total = 0;
    System.out.println("The list:");
    while (list != null) {
        total++;
        System.out.println(total + ". " + list.data);
        list = list.next;
    }
    list = head;
    
    // test various values for k    
    int[] k_values = new int[6];
    k_values[0] = 6;
    k_values[1] = 9;
    k_values[2] = 4;
    k_values[3] = 2;
    k_values[4] = 0;

    for (int i = 0; i < k_values.length; i++) {
        int difference = total - k_values[i];
        list = head;
        count = 1;
        while (list != null && count != difference) {
            list = list.next
            count++;
        }
        System.out.println("\nThe node k = " + k_values[i] + " spots from the end of the list is: ");
        System.out.println(list.data);
    }
}