Sunday 15 March 2015

Rotate a linked list anti clock wise for given number of nodes


Java program to rotate a given Linked list anti clockwise for given no of nodes.
/**
 * @author vikky.agrawal
  */

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));
		}
		this.rotateACW(node, 8);
	}
	
	/**
	 * Rotate a linked list Anti clock wise for given number of nodes
	 */

	public void rotateACW(Node root, int n) {

		if (root == null || n<=0) {
			return;
		}

		int size=size(root);
		if(n==size){
			//no need to rotate, as it will be the same
			System.out.println("List after rotating");
			print(root);
			return;			
		}
		
		if (n > size) {
			n=n%size;
		}

		System.out.println("List Before rotating");
		print(root);

		Node ptr = root;
		Node ptr1 = null;

		while (n-- > 0) {
			ptr1 = ptr;
			ptr = ptr.getLink();
		}

		Node temp = ptr;

		while (temp.getLink() != null) {
			temp = temp.getLink();
		}

		temp.setLink(root);
		ptr1.setLink(null);
		root = ptr;

		System.out.println("List after rotating");
		print(root);

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

No comments:

Post a Comment