
public class LinkedList<T> {

	private Node<T> head=null;
	private int size;

	/*public void print(){
		if(head==null)
			System.out.println("No Nodes");
		else{
			Node<T> pos= head;
			while(pos!=null){
				System.out.println(pos.toString());
				pos=pos.getNext();
			}
		}
	}*/
	public void print(){
		print(head);
	}


	public void print(Node<T> pos){

		System.out.println(pos.toString());
		if(pos!=null && pos.getNext()!=null)
			print(pos.getNext());
	}

	public LinkedList<T> reverse(LinkedList<T> list){
		return reverse(list, 0);
	}


	private LinkedList<T> reverse(LinkedList<T> list,int times){
		if(list==null || list.getSize()==1 || times==list.getSize()){
			return list;
		}
		Node<T> pos=list.getNode(list.getSize()-1);
		list.add(pos.getData(), times);
		list.delete(list.getSize()-1);

		return reverse(list,++times);


	}
	
	public void rev(Node<T> curr,Node<T> prev){
		if(curr!=null){
			rev(curr.next,curr);
			curr.next=prev;
		}
		else{
			head=prev;
		}
	}


	//	public Node<T> reverseList(Node<T> head) {
	//	    if(head==null || head.getNext() == null)
	//	        return head;
	//	 
	//	    //get second node    
	//	    Node<T> second = head.getNext();
	//	    //set first's next to be null
	//	    head = null;
	//	 
	//	    Node<T> rest = reverseList(second);
	//	    second.setNext(head);
	//	 
	//	    return rest;
	//	}
	//	public Node<T> reverseList(Node<T> head) {
	//		if(head==null || head.next == null)
	//		return head;
	//		
	//		Node<T> second = head.getNext();
	//		Node<T> rest = reverseList(second);
	//		head.next.next = head;
	//		head.next = null;
	//
	//		return rest;
	//		}
	public Node<T> getNode(int index){
		Node<T> pos=head;
		for (int i = 0; i < index; i++) {
			pos=pos.getNext();
		}
		return pos;
	}

	public boolean add(T data){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(head==null){
			head=newNode;
			++size;
			return true;
		}
		while(pos.getNext()!=null){
			pos=pos.getNext();
		}

		pos.setNext(newNode);
		++size;
		return true;

	}


	public boolean add(T data,int index){
		Node<T> newNode = new Node<>(data);
		Node<T> pos=head;
		if(index <0 || index > size)
			return false;

		if(index==0){
			++size;
			newNode.setNext(head);
			head=newNode; 
			return true;

		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		newNode.setNext(pos.getNext());
		pos.setNext(newNode);
		++size;
		return true;

	}

	public int getIndex(T data){
		Node<T> pos=head;
		int index=0;
	
		while(pos!=null){
	
			if(pos.equal(data)){
				return index;
			}
	
			pos=pos.getNext();
			++index;
	
		}
		return -1;
	}


	public boolean delete(int index){
		if(index <0 || index > size)
			return false;
		Node<T> pos=head;
		if(index==0){
			--size;
			head=head.getNext();
			return true;
		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		--size;
		pos.setNext(pos.getNext().getNext());
		return true;

	}

	public boolean deleteData(T data){

		int index = getIndex(data);
		if(index==-1)
			return false;
		Node<T> pos=head;
		if(index==0){
			--size;
			head=head.getNext();
			return true;
		}
		for(int i=0;i<index-1;++i){
			pos=pos.getNext();
		}
		--size;
		pos.setNext(pos.getNext().getNext());
		return true;


	}

	public T getIndexData(int index){
		if(index<0 || index>=size)
			return null;
		Node<T> pos= head;
		if(index==0){
			return pos.getData();
		}
		for(int i=0;i<index;++i){
			pos=pos.getNext();
		}
		return pos.getData();
	}



	public Node<T> getHead() {
		return head;
	}

	public int getSize() {
		return size;
	}

	public static void print(LinkedList<Integer> l1,LinkedList<Integer> l2){
		Node<Integer> pos2 = l2.getHead();

		while(pos2!=null){
			int index = pos2.getData();
			Integer s = l1.getIndexData(index);
			if(s!=null)
				System.out.println(s);
			pos2=pos2.getNext();
		}
	}

	public void removeDuplicate(LinkedList<Integer> l){
		Node<Integer> pos= l.getHead();

		while(pos != null){

			Node<Integer> rr = pos.getNext();
			Node<Integer> prev = pos;

			while(rr != null){
				if(pos.data == rr.data){
					prev.next = rr.next;
					rr = rr.getNext();
				}
				else{
					rr = rr.getNext();
					prev = prev.getNext();
				}
			}
			pos=pos.getNext();

		}
	}





}
