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 func 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 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

Provide us with the algorithm and we'll explain it:) I am assuming you can't change the data strucutre to doubly linked list in which case reversal would be almost trivial.

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

Answer 3

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 second element on 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 4

The algo will need to work on the following model,

• keep track of the head
• Recurse till end of linklist
• Reverse linkage

Head

|

1-->2-->3-->4-->N-->null

null-->1-->2-->3-->4-->N<--null

null-->1-->2-->3-->4<--N<--null

null-->1-->2-->3<--4<--N<--null

null-->1-->2<--3<--4<--N<--null

null-->1<--2<--3<--4<--N<--null

null<--1<--2<--3<--4<--N

               |
              Head



public ListNode reverse(ListNode toBeNextNode, ListNode currentNode){

     ListNode currentHead = currentNode; // keep track of the head
     if((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1
     if(currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively
     currentNode.next = toBeNextNode; // reverse link
     return currentHead;


}

System.out

head-->12345

head-->54321

Answer 5

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

Answer 6

void reverse(node1,node2){
if(node1.next!=null)
      reverse(node1.next,node1);
   node1.next=node2;
}
call this method as reverse(start,null);

Answer 7

Comprehsive solution for reversing a Singly Linked List can be found here with illustrative pictures and complete working code.

http://www.technicalypto.com/2010/03/reverse-singly-linked-list-recursively.html

Answer 8

I think this is more cleaner solution, which resembles LISP

//Example:
// reverse0(1->2->3, null) => 
//      reverse0(2->3, 1) => 
//          reverse0(3, 2->1) => reverse0(null, 3->2->1)
// once the first argument is null, return the second arg
// which is nothing but the reveresed list.

Link reverse0(Link f, Link n) {
    if (f != null) {
        Link t = new Link(f.data1, f.data2); 
        t.nextLink = n;                      
        f = f.nextLink;             // assuming first had n elements before, 
                                    // now it has (n-1) elements
        reverse0(f, t);
    }
    return n;
}

Answer 9

I know this is an old post, but most of the answers are not tail recursive i.e. they do some operations after returning from the recursive call, and hence not the most efficient.

Here is a tail recursive version:

public Node reverse(Node previous, Node current) {
    if(previous == null)
        return null;
    if(previous.equals(head))
        previous.setNext(null);
    if(current == null) {    // end of list
        head = previous;
        return head;
    } else {
        current.setNext(previous);
        reverse(current, current.getNext());
    }
    return null;    //should never reach here.
} 

Call with:

Node newHead = reverse(head, head.getNext());