Data Structure Recursion

[Christ1m]

Java:

public class lp { public int first; public lp rest; public lp(int first, lp rest) { this.rest = rest; this.first = first; }

I need help on this recursive function.
If the input is empty, return null. Otherwise, use a recursive call to reverse the list head.rest, then use the append function(assuming that it exists) to add head.first to the end of the reversed list. The second argument of append is a list -- not a number. But you can make a list of length one, containing only the number head.first. Then you can use append to add this list to the end of another list.

Java:

public static lp reverse(lp head) { if(head==null) {     return null;   } // Im lost after this part.....  else    { // return append(head.rest,reverse(head.rest));      return new lp(head.first,reverse(head.rest));    } if{ //something...... } else{ //something... } }

[DemonWasp]

1. If the input is empty, return null - done!
2. Use recursive call to reverse head.rest - done!
3. Add head.first to the end of the reversed list - not quite.

You need to think about how to accomplish step #3. Try it on paper.

[Prabhakar Ragde]

There is a more efficient recursive solution.