Sunday, 15 March 2015

LinkedList : print middle element and print nth element from last


Java program having functions to print middle element of linked list(using slow and fast pointers) and printing nth element from last of linked list.

/**
 * @author vikky.agrawal
 * Link List print middle element | print nth element from last
 */

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("Middle in case of even no of elements:");		
		printMiddle(node);
		add(node, 65);
		System.out.println("Middle in case of odd no of elements:");
		printMiddle(node);
		printNthFromLast(node, 5);
	}
	
	
	//Print Nth element from last for given value of N	
	
	
	public void printNthFromLast(Node root, int n) {

		int i = n;
		if (root == null) {
			return;
		}

		if (i > size(root)) {
			System.out.println("Not enough elements");
			return;
		}

		Node node = root;
		Node nodeback = root;

		while ((node.getLink() != null) && (--i > 0)) {
			node = node.getLink();
		}

		if (node.getLink() != null) {
			while (node.getLink() != null) {
				nodeback = nodeback.getLink();
				node = node.getLink();
			}
		}

		System.out.println("N = " + n + " element from last is :"
				+ nodeback.getData());

	}

	/**
	 * Print middle element using slow and fast pointers.
	 */

	public void printMiddle(Node root) {
		if (root == null) {
			return;
		}

		System.out.println("Linked list is ");
		print(root);

		Node hare = null;
		Node tortoise = null;
		boolean temp = false;
		if (size(root) % 2 == 0)
			temp = true;

		if (temp) {
			hare = root.getLink();
			tortoise = root;
		} else {
			hare = root;
			tortoise = root;
		}

		while (hare != null && hare.getLink() != null) {
			hare = hare.getLink().getLink();
			tortoise = tortoise.getLink();
		 }
		if (temp) {
			System.out.println("Middle elements :" + tortoise.getData()
					+ " and " + tortoise.getLink().getData());
		} else {
			System.out.println("Middle element is :" + tortoise.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;
		    }  
	}
	
}