public class MyLinkedList
{
	private ListNode head;

	public MyLinkedList()
	{
		head = null;
	}

	public boolean isEmpty()
	{
		return head == null;
	}

	public void addAtFront(Object o)
	{
		head = new ListNode(o,head);
	}

	/*
	public void addAtEnd(Object o)
	{
		if (head == null)
			head = new ListNode(o);
		else
		{
			ListNode curr = head;
			while (curr.getNext() != null)
				curr = curr.getNext();
			curr.setNext(new ListNode(o,null));
		}
	}
	*/

	public void addAtEnd(Object o)
	{
		head = addHelper(head,o);
	}

	private ListNode addHelper(ListNode h, Object o)
	{
		if (h == null)
			return new ListNode(o,null);

		h.setNext(addHelper(h.getNext(),o));
		return h;
	}

	public void addInOrder(Object o)
	{
		head = orderedHelper(head,o);
	}

	private ListNode orderedHelper(ListNode hd, Object o)
	{
		if (hd == null || ((Comparable)o).compareTo(hd.getValue()) < 0)
		    return new ListNode(o,hd);

		hd.setNext(orderedHelper(hd.getNext(),o));
		return hd;
    }

	public void addList(MyLinkedList l)
	{
		ListNode curr = l.head;
		while (curr != null)
		{
			addAtFront(curr.getValue());
			curr = curr.getNext();
		}
	}

	/*
	public Object find(Object key)
	{
		for (ListNode curr = head; curr != null; curr = curr.getNext())
		{
			if (curr.getValue().equals(key))
				return curr.getValue();
		}
		return null;
	}
	*/

	public Object find(Object key)
	{
		return findHelper(head,key);
	}

	private Object findHelper(ListNode h, Object key)
	{
		if (h == null)
			return null;

		if (h.getValue().equals(key))
			return h.getValue();

		return findHelper(h.getNext(),key);
	}

	/*
	public boolean remove(Object o)
	{
		if (head == null)	// empty list
			return false;

		if (head.getValue().equals(o))
		{	// node to be deleted is first node
			head = head.getNext();
			return true;
		}

		for (ListNode curr = head; curr.getNext() != null; curr = curr.getNext())
			if (curr.getNext().getValue().equals(o))
			{
				curr.setNext(curr.getNext().getNext());
				return true;
			}

		return false;
	}
	*/

	public boolean remove(Object o)
	{
		try
		{
		    head = removeHelper(head,o);
		    return true;
		}
		catch (java.util.NoSuchElementException n)
		{
		    return false;
		}
    }

	/*
	private ListNode removeHelper(ListNode h, Object o)
	{
		if (h == null)
			throw new java.util.NoSuchElementException();

		// this version is written in the "only 1 return" idiom
		if (h.getValue().equals(o))
			h = h.getNext();
		else
			h.setNext(removeHelper(h.getNext(),o));
			
		return h;
	}
	*/
	
	private ListNode removeHelper(ListNode h, Object o)
	{
		if (h == null)
			throw new java.util.NoSuchElementException();
		
		// this version is written in the "return if done" idiom
		if (h.getValue().equals(o))
			return h.getNext();
		
		h.setNext(removeHelper(h.getNext(),o));
		return h;
	}
	
	// Reverse a linked list in linear time.
	public void reverse()
	{
		head = reverseHelper(head);
	}
	
    public ListNode reverseHelper(ListNode h)
    {
		if (h != null && h.getNext() != null)
		{
			ListNode last = reverseHelper(h.getNext());
			h.getNext().setNext(h);
			h.setNext(null);
			return last;
		}
		return h;
    }
    
    // Splits its list into two pieces
	public MyLinkedList split()
	{
		int count = 0;
		ListNode h = this.head;
		
		// count the nodes
		while (h != null)
		{
			count ++;
			h = h.getNext();
		}
		
		// determine midpoint number
		//int mid = (count % 2 == 0) ? (count / 2) : ((count / 2) + 1);
		int mid = (count + 1) / 2;
		
		// go halfway in this list, make new list and fix up end of first half
		MyLinkedList result = new MyLinkedList();
		h = this.head;
				
		if (h != null)	// if null, no work to split
		{
			for (int i = 0; i < mid - 1; i++)
				h = h.getNext();
			
			result.head = h.getNext();
			h.setNext(null);
		}
		
		return result;
	}
	
	/*
	// for recursion/helper function illustration purposes ONLY; 
	// not meant to be a supported method of MyLinkedList
	public void display()
	{
		displayHelper(head);
	}
	
	private void displayHelper(ListNode h)
	{
		if (h == null)
			System.out.println();
		else
		{
			System.out.print("\t" + h.getValue());
			displayHelper(h.getNext());
		}
	}
	*/

	public String toString()
	{
		String result = "";

		for (ListNode curr = head; curr != null; curr = curr.getNext())
		{
			result += curr.getValue();
			if (curr.getNext() != null)
				result += " --> ";
		}

		return result;
	}

	public static void main(String[] args)
	{
		MyLinkedList l = new MyLinkedList();

		l.addAtFront("minion");
		l.addAtEnd("of");
		l.addAtEnd("Zuul");
		l.addAtFront("Gozer");
		System.out.println(l);
		l.reverse();
		System.out.println(l);
	}
}