Is it possible to implement an algorithm to find the nth to last element of a singly linked list using recursion in java

Question

I know that you can simply solve this question iteratively by using a counter to increment each time you pass a node in linkedlist; also creating an arraylist and setting the data found with each node inside it. Once you hit the tail of the linkedlist, just minus the Nth term from the total number of elements in the arraylist and you will be able to return the answer. However how would someone perform this using recursion? Is it possible and if so please show the code to show your genius :).

Note: I know you cannot return two values in Java (but in C/C++, you can play with pointers :])

Edit: This was a simple question I found online but I added the recursion piece to make it a challenge for myself which I've come to find out that it may be impossible with Java.

Answer 1

The trick is to do the work after the recursion. The array in the private method is basically used as a reference to a mutable integer.

class Node {
  Node next;
  int data;

  public Node findNthFromLast(int n) {
    return findNthFromLast(new int[] {n});
  }

  private Node findNthFromLast(int[]?r) {
    Node result = next == null ? null : next.findNthFromLast(r);
    return r[0]-- == 0 ? this : result;  
  }
}