Reversing a linked list in Java, recursively

Question

I have been working on a Java project for a class for a while now. It is an implementation of a linked list (here called AddressList, containing simple nodes called ListNode). The catch is that everything would have to be done with recursive algorithms. I was able to do everything fine sans one method: public AddressList reverse()

ListNode:

public class ListNode{   public String data;   public ListNode next; } 

Right now my reverse function just calls a helper function that takes an argument to allow recursion.

public AddressList reverse(){   return new AddressList(this.reverse(this.head)); } 

With my helper function having the signature of private ListNode reverse(ListNode current).

At the moment, I have it working iteratively using a stack, but this is not what the specification requires. I had found an algorithm in C that recursively reversed and converted it to Java code by hand, and it worked, but I had no understanding of it.

Edit: Nevermind, I figured it out in the meantime.

private AddressList reverse(ListNode current, AddressList reversedList){   if(current == null)        return reversedList;   reversedList.addToFront(current.getData());   return this.reverse(current.getNext(), reversedList); } 

While I'm here, does anyone see any problems with this route?

Answer 1

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

Answer 2

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->null it 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