Reversing a linked list in Java, recursively

There's code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper):

1. What is the reverse of null (the empty list)? null.
2. What is the reverse of a one element list? the element.
3. What is the reverse of an n element list? the reverse of the rest of the list followed by the first element.

public ListNode Reverse(ListNode list){    if (list == null) return null; // first question    if (list.next == null) return list; // second question    // third question - in Lisp this is easy, but we don't have cons    // so we grab the second element (which will be the last after we reverse it)    ListNode secondElem = list.next;    // bug fix - need to unlink list from the rest or you will get a cycle    list.next = null;    // then we reverse everything from the second element on    ListNode reverseRest = Reverse(secondElem);    // then we join the two lists    secondElem.next = list;    return reverseRest;}

I was asked this question at an interview and was annoyed that I fumbled with it since I was a little nervous.

This should reverse a singly linked list, called with reverse(head,NULL);so if this were your list:

1->2->3->4->5->nullit would become:5->4->3->2->1->null

    //Takes as parameters a node in a linked list, and p, the previous node in that list    //returns the head of the new list    Node reverse(Node n,Node p){           if(n==null) return null;        if(n.next==null){ //if this is the end of the list, then this is the new head            n.next=p;            return n;        }        Node r=reverse(n.next,n);  //call reverse for the next node,                                       //using yourself as the previous node        n.next=p;                     //Set your next node to be the previous node         return r;                     //Return the head of the new list    }    

edit: ive done like 6 edits on this, showing that it's still a little tricky for me lol

I got half way through (till null, and one node as suggested by plinth), but lost track after making recursive call. However, after reading the post by plinth, here is what I came up with:

Node reverse(Node head) {  // if head is null or only one node, it's reverse of itself.  if ( (head==null) || (head.next == null) ) return head;  // reverse the sub-list leaving the head node.  Node reverse = reverse(head.next);  // head.next still points to the last element of reversed sub-list.  // so move the head to end.  head.next.next = head;  // point last node to nil, (get rid of cycles)  head.next = null;  return reverse;}