Thursday, September 27, 2018

LinkedList - Reverse (recursion and iterative)

Recursive Approach

//2->4->5->6->7->8
   public Node reverseTheLinkedlist(Node nd){    
  if(nd.nextNd==null)
  return nd;
   
  Node remaining = reverseTheLinkedlist(nd.nextNd);
  System.out.println("The value of remaining is : "+remaining.value);
       nd.nextNd.nextNd=nd;
       nd.nextNd=null;
  return remaining;

   }

1) In the above program, first we check if the node sent in the program argument is null or the next value to that node is null. If so, then we return the node sent in the function argument.

2) remaining -- The value of this node in this program will basically become the last node in the list. Here remaining will become 8.

3) In each return cycle of recursion (except the last node), node is swipped with its next value and the node is then set to null.

The program will work in the following way:-

remaining = 8
Cycle 1 : 8->7->null

remaining = 8
Cycle 2 : 7->6, so result will become 8->7->6

remaining = 8
Cycle 3 : 6->5, so result will become 8->7->6->5

likewise, it will work for node 2 & 4 also.

Iterative Approach

This is the iterative approach:-

public Node reverseTheLinkedList(Node nd){
Node current = nd;
Node previous=null;
Node next=null;
while(current!=null){
next=current.next;
current.next=previous;
            previous=current;
            current=next;
}
return previous;

}

No comments:

Post a Comment