Friday 27 February 2015

Reverse a LinkedList : recursive and iterative in java

Given a LinkedList reverse it
1. Iterative.
2. Recursive.


/**
* @author vikky.agrawal
* Link List reversal | Iterative and Recursive.
*/

public class LinkedList {

Node node = null;

public static void main(String[] args) {

        LinkedList list = new LinkedList();
        list.operations();

    }

    public void operations() {

        this.node = new Node(10);

        for (int i = 1; i < 6; i++) {
            add(node, (int) (Math.random() * 100));
        }

        System.out.println("Test: iterative, List before reversal");
        print(node);
        this.node=reverse(node); 
    
        
        System.out.println("Test: recursive, List before reversal");
        print(node);
        this.node=this.recursiveReverse(node);
        System.out.println("After recursice reverse list is : ");
        print(node); 
    }
    
    /**
     * Reverse a linked list iterative.
     * Using auxiliary pointers.
     */
    
    public Node reverse(Node ptr) {

        if (ptr == null) {
            System.out.println("List is empty:returning");
            return null;
        }
        Node ptr1 = ptr;
        Node ptr2 = ptr;
        Node ptr3 = null;

        while (ptr1.getLink() != null) {
            ptr2 = ptr1;
            ptr1 = ptr1.getLink();
            ptr2.setLink(ptr3);
            ptr3 = ptr2;

        }
        ptr1.setLink(ptr2); //setting link for the last node;

        System.out.println("Reversed List :");
        this.print(ptr1);
        return ptr1;
    }
    
    /**
     * RecursiveReverse() 
     * Use cases:
     * What is the reverse of null (the empty list)? null.
     * What is the reverse of a one element list? the element. 
     * What is the reverse of an n element list?
     * the reverse of the second element on
     * followed by the first element.
     */

    public Node recursiveReverse(Node root) {

        // base case

        if (root == null || root.getLink() == null) {
            return root;
        }
        Node temp = recursiveReverse(root.getLink());

        // temp contains last element when recursion done
        // take 2 nodes and dry-run
        root.getLink().setLink(root);
        root.setLink(null);
        return temp;

    }
    
    /**
     *  Print reverse of the link list 
     *  reccursively
     */
    
    public void printReverseRecursive(Node root){

        if(root.getLink()!=null){
            printReverseRecursive(root.getLink());
            System.out.println(root.getData());
        }else{
            System.out.println(root.getData());
        }
    }

    /**
     * Helper functions for LinkedList
     */
    public void add(Node ptr, int data) {
        if (ptr == null) {
            System.out.println("Always null ?");
            ptr = new Node(data);
        } else {
            Node newptr = ptr;
            while (newptr.getLink() != null) {
                newptr = newptr.getLink();
            }
            newptr.setLink(new Node(data));
            newptr.getLink().setLink(null);
        }
    }

    public void print(Node ptr) {

  if (ptr == null) {
   return;
  }
  Node ptr1 = ptr;
  System.out.print(ptr1.getData() + "->");
  while ((ptr1 = ptr1.getLink()) != null) {
   System.out.print(ptr1.getData() + "->");
  }
  System.out.println("/n");

 }
public int size(Node ptr) {

        if (ptr == null) {
            return -1;
        }
        Node ptr1 = ptr;
        int i = 1;
        while ((ptr1 = ptr1.getLink()) != null) {
            i++;
        }
        return i;
    }

        /**
     * static inner class for LinkedList 
     * Data Structure
     */
    private static class Node{
         private int data;
         private Node link;         
            
            Node(){
                        
            }
            
            Node(int data){
                //mergedList=new Node();
                this.setData(data);
                this.setLink(null);       
            }
            
            public int getData(){
                return this.data;
            }
              
            public Node getLink(){
                return this.link;
            }
            
            public void setData(int data){
                this.data=data;
            }       
            
            public void setLink(Node link){
                this.link=link;
            }  
    }
    
}