Recursively find nth to last element in linked list

java, linked-list, recursion

Solution

You need to go to the end and then count your way back, make sure to pass back the node each time its passed back. I like one return point

public static int i = 0;  
public static Link.Node findnthToLastRecursion(Link.Node node, int pos) {

    Link.Node result = node;

    if(node != null) {
        result = findnthToLastRecursion(node.next, pos);

        if(i++ == pos){
            result = node;
        }
    }
    return result;
}

Working example outputs 7 as 2 away from the 9th and last node:

public class NodeTest {

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    Node first = null;
    Node prev = null;
    for (int i = 0; i < 10; i++) {

        Node current = new Node(prev, Integer.toString(i),null);
        if(i==0){
            first = current;
        }
        if(prev != null){
            prev.next = current;
        }
        prev = current;
    }

    System.out.println( findnthToLastRecursion(first,2).item);
}

public static int i = 0;

public static Node findnthToLastRecursion(Node node, int pos) {

    Node result = node;

    if (node != null) {
        result = findnthToLastRecursion(node.next, pos);

        if (i++ == pos) {
            result = node;
        }
    }

    return result;
}
}

Problem

I'm practicing basic data structure stuff and I'm having some difficulties with recursion. I understand how to do this through iteration but all of my attempts to return the nth node from the last of a linked list via recursion result in null. This is my code so far: ``` public static int i = 0; public static Link.Node findnthToLastRecursion(Link.Node node, int pos) { if(node == null) return null; else{ findnthToLastRecursion(node.next(), pos); if(++i == pos) return node; return null; } ``` Can anyone help me understand where I'm going wrong here? This is my iterative solution which works fine, but I'd really like to know how to translate this into recursion: ``` public static Link.Node findnthToLast(Link.Node head, int n) { if (n < 1 || head == null) { return null; } Link.Node pntr1 = head, pntr2 = head; for (int i = 0; i < n - 1; i++) { if (pntr2 == null) { return null; } else { pntr2 = pntr2.next(); } } while (pntr2.next() != null) { pntr1 = pntr1.next(); pntr2 = pntr2.next(); } return pntr1; } ```

Original source