Recursively find nth to last element in linked list

Question

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;
}

Solution 1

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;
}
}

Solution 2

No need for static variables.

public class List {
    private Node head = null;

    // [...] Other methods

    public Node findNthLastRecursive(int nth) {
        if (nth <= 0) return null;
        return this.findNthLastRecursive(this.head, nth, new int[] {0});
    }

    private Node findNthLastRecursive(Node p, int nth, int[] pos) {
        if (p == null) {
            return null;
        }
        Node n = findNthLastRecursive(p.next, nth, pos);
        pos[0]++;
        if (pos[0] == nth) {
            n = p;
        }
        return n;
    }
}

Solution 3

I misunderstood the question. Here is an answer based on your iterative solution:

public static Link.Node findnthToLast(Link.Node head, int n) {
    return findnthToLastHelper(head, head, n);
}

private static Link.Node findnthToLastHelper(Link.Node head, Link.Node end, int n) {
    if ( end == null ) {
        return ( n > 0 ? null : head);
    } elseif ( n > 0 ) {
        return findnthToLastHelper(head, end.next(), n-1);
    } else {
        return findnthToLastHelper(head.next(), end.next(), 0);
    }
}

Solution 4

You can do this a couple of ways:

1. recurse through the list once to find the list length, then write a recursive method to return the k^th element (a much easier problem).

2. use an auxiliary structure to hold the result plus the remaining length; this essentially replaces the two recursions of the first option with a single recursion:

   static class State {
       Link.Node result;
       int trailingLength;
   }
   public static Link.Node findnthToLastRecursion(Link.Node node, int pos) {
       if(node == null) return null;
       State state = new State();
       findnthToLastRecursion(node, pos, state);
       return state.result;
   }
   
   private static void findnthToLastRecursion(Link.Node node, int pos, State state) {
       if (node == null) {
           state.trailingLength = 0;
       } else {
           findnthToLastRecursion(node.next(), state);
           if (pos == state.trailingLength) {
               state.result = node;
           }
           ++state.trailingLength;
       }
   }
   

View more solutions

Comments

[Floris]

What is the value of node when you first call - and are you working forward or backwards? I would have thought that you need to start at the end and call previous(), or if you don't know what the end is, start at the beginning, work your way to the end, then back out n times. This code doesn't do anything like that...

[justderb]

How do you know the nth last node when you don't find where the last node is (or the size)? This (if written correctly) will find the nth - 1 node (not nth last node)

[Sam I am says Reinstate Monica]

quick question: do you know what the length of your linked list is

[user3029486]

The initial value is the head and there's no previous() function to call. Starting at the beginning, working way to end, then backing out n times makes sense to me by iteration but I just can't seem to wrap my head on how to do that recursively.

[user3029486]

In this case I do know the length, but I'm trying to write it under the assumption that the length is unknown.

[Sam I am says Reinstate Monica]

@user3029486 personally, I don't think that there's a good way to do this recursively. Yes, there are ways, but none of them are good

[Sam Nunnally]

the node returned from when i and pos are equal is never returned back up the stack. See my answer below.

[Sylwester]

So I imagine you get a one element list if you pass it findnthToLast(lst, 1) but according to the iterative solution you have the for loop will exit since the test 0 < 1-1 won't pass. Is that an error?

[user3029486]

Hm, good catch. I did switch it to test with 1 and it's returning the right thing. I'm actually a bit confused as to why now. . .

[Sylwester]

@user3029486 I works because you don't check pntr2 != null but pntr2.next() :)

[Sam I am says Reinstate Monica]

nth to last; not nth

[user3029486]

Thank you, this makes a lot more sense now. Looks like knowing the length and using an auxiliary function are the keys to this.

[Trying]

@user3029486 very true.

[OpenUserX03]

This should be the accepted answer since recursion without a helper function demonstrates a better understanding of recursion if it's an interview question.

[Lorenzo Polidori]

@OpenUserX03 Well, the helper here is the static int i. This can be done without static variables: stackoverflow.com/a/29937328/885464

[michal]

What's the difference between having a static variable and adding an extra argument/having a helper function? I don't see why the latter should be better than the former.

[Lorenzo Polidori]

@michal Of course using a static variable would work, but that wouldn't be a perfectly recursive approach strictly speaking. Using the stack to keep the current state of the recursion is usually considered the common practice.

[michal]

I mean, you are also using an additional variable, you call it pos. Regardless if it is static or you pass it around from call to call, doesn't change much. In other words, both methods resort to extra variables beyond the call stack. Do you see what I mean?

[venk]

I think this approach is better because it avoids the addition of a static variable at the class level. The "findNthRecursive()" function is likely to be just one among several other member functions in the "LinkedList" class. So, adding a static variable at the class level just for this function doesn't appear clean/ minimal enough. Having said that, i am not yet clear as to why pos needs to be of type int[]. Why cant it be just an int?