Saturday, March 6, 2010

Reverse a Singly Linked List Recursively in Java

We have already seen how to reverse a singly linked list with illustrative pictures. Now lets see how we can do it recursively. In the previous problem we did it iteratively, now we shall do it recursively.
To attack any problem in a recursive approach, we need to be very clear about the end/boundary conditions. For a linked list, reverse of a null list or reverse of list of size 1 is going to be the same.
Reverse of a linked list of size x will be the reverse of the 'next' element followed by first.
A picture means a thousand words. So, here is what happens internally.

Now for the comprehensive Java code (reference for SinglyLinkedList implementation can be found here)

package dsa.linkedlist;

public class ReverseLinkedListRecursively {
 
 public static void main(String args[]){
  ReverseLinkedListRecursively reverser = new ReverseLinkedListRecursively();
  SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);
  System.out.println("Original List : "+originalList.toString());
  originalList.start = reverser.reverse(originalList.start);
  System.out.println("Reversed List : "+originalList.toString());
 }
 
 public Node<Integer> reverse(Node<Integer> list)
 {
     if (list == null || list.next==null) return list;
     Node<Integer> nextItem = list.next;
     list.next = null;
     Node<Integer> reverseRest = reverse(nextItem);
     nextItem.next = list;
     return reverseRest;
 }

 
 private SinglyLinkedList<Integer> getLabRatList(int count){
  SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();
  for(int i=0;i<count;i++){
   sampleList.add(i);
  }
  return sampleList;
 }
}
/*
 * SAMPLE OUTPUT
 * Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
 * Reversed List : 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
 */

Cheers,
Bragaadeesh.

8 comments:

Crazy as you can imagine said...

Valuable! Concise and great graph illustration! Thanks for your good work!

bragadeesh said...

Good to see that it helped you!!

gen said...

Very Nice Blog.

Reverse can be done this way too..

node reverse(node n)
{

if(n==null || n.next == null)
return n;

reverse(n.next);
n.next.next = n;
n.next = null;

return n;
}

b said...

@gen: Thanks for your feedback! Your code is more simpler and neater..

Varun Pathak said...

@gen
your code although is reversing the list, its returning the tail pointer of the reversed list. Their is no way to access its head.

Neco said...

Hi, consider this:

public class Lists {

public static void main(String[] args) {

Node nodeE = new Node("e", null);
Node nodeD = new Node("d", nodeE);
Node nodeC = new Node("c", nodeD);
Node nodeB = new Node("b", nodeC);
Node nodeA = new Node("a", nodeB);

Node node = reverse(nodeA);

while (node != null) {
System.out.println(node.getValue());
node = node.getNext();
}
}

public static Node reverse(Node head) {

return recursiveHelper(null, head);
}

private static Node recursiveHelper(Node prev, Node curr) {

if (curr == null) {

return prev;

} else {

Node next = curr.getNext();
curr.setNext(prev);

return recursiveHelper(curr, next);
}
}
}

whizz.comp said...

@Varun -
Good catch dude - i have the same opinion as you - but here's a fix.

public static Node ReverseLinkedListRec(Node nd)
{
if (nd == null || nd.Link == null) return null;

Node nextNode = nd.Link;

nd.Link = null;

Node retNode = ReverseLinkedListRec(nextNode);

nextNode.Link = nd;

return retNode == null ? nextNode : retNode;
}

Harish Pulla said...

package com.list;


public class LinkedListImpl {

public Node headNode = null;

public void insert(int data)
{
Node vNode = new Node();
vNode.setData(data);
vNode.setNext(headNode);
headNode = vNode ;
}

public void display()
{
Node vCurr = headNode ;
while(vCurr != null )
{
System.out.print(vCurr.getData()+" ");
vCurr = vCurr.getNext() ;
}
System.out.println();
}

public void reverseList(Node vCurr)
{
if(vCurr==null)
return;

Node vPrev = vCurr ;
vCurr = vCurr.getNext();

if(vCurr == null)
return ;

if(vCurr.getNext() == null)
{
headNode = vCurr;
}

reverseList(vCurr);

vCurr.setNext(vPrev);
vPrev.setNext(null);




}


public static void main(String args[])
{
LinkedListImpl impl = new LinkedListImpl();
for(int i=0;i<10;i++)
{
impl.insert(i);
}
impl.display();
impl.reverseList(impl.headNode);
System.out.println("After Reverse the list is as follows ");
impl.display();
}



}


package com.list;

public class Node {

private Integer data ;
private Node next;

public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}


}