package linkedlist;


public class NthFromLastNode {

    /*
     * Given a singly linked list, return nth from last node. Return null if 'n' is out-of-bounds.
     * Eg: Input:  67, 9, 72, 94, 13, 59, 55, 72, 66, 22
     *     Output: Result for n=5 is 59
     *             Result for n=6 is 13
     *             Result for n=4 is 55
     *             Result for n=10 is 67
     * */

    /*
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * Constant, O(1)
     *
     *    Use two pointers to find the nth from the last node.
     *    one pointing to the head and the other pointing to the nth node.
     *    Move both pointers forward until the second pointer reaches the tail.
     *    Now the first pointer will be pointing to the nth node from last.
     *    And if tail is reached before making both pointers n nodes apart, that means
     *    n is out of bounds.
     * */

   public static class LinkedList {
        Node head;

        /* Function to get the nth node from end of list */
        void printNthFromLast(int n) {
            Node main_ptr = head;
            Node ref_ptr = head;

            int count = 0;
            if (head != null) {
                while (count < n) {
                    if (ref_ptr == null) {
                        System.out.println(n + " is greater than the no " +
                                " of nodes in the list");
                        return;
                    }
                    ref_ptr = ref_ptr.next;
                    count++;
                }
                while (ref_ptr != null) {
                    main_ptr = main_ptr.next;
                    ref_ptr = ref_ptr.next;
                }
                System.out.println("Node no. " + n + " from last is " +
                        main_ptr.data);
            }
        }

        /* Inserts a new Node at front of the list. */
        public void push(int new_data) {
        /*
         * 1 & 2: Allocate the Node & Put in the data
         * */
            Node new_node = new Node(new_data);

        /*
         * 3. Make next of new Node as head
         * */
            new_node.next = head;

        /*
         * 4. Move the head to point to new Node
         * */
            head = new_node;
        }


       public class Node {
            int data;
            Node next;

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


    public static void main(String[] args) {
        LinkedList llist = new LinkedList();
        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(35);

        llist.printNthFromLast(4);
    }
}