import java.util.*;

class BasicLinkedList <E> implements ListInterface <E> {
	
	public BasicLinkedList<E> split() {
		BasicLinkedList<E> backList = new BasicLinkedList<E>();
		if (head == null) // if 0 nodes
			return backList;
		ListNode<E> thisTail = head; 
		ListNode<E> currNode = head.getNext();
		while (currNode != null && currNode.getNext() != null) {
			thisTail = thisTail.getNext(); // this loop works for >=1 node
			currNode = currNode.getNext().getNext();
		}
		backList.head = thisTail.getNext();
		thisTail.setNext(null);
		return backList;
	}
	
	public static BasicLinkedList<Integer> merge(
		BasicLinkedList<Integer> firstList,
		BasicLinkedList<Integer> secondList) {
	
		ListNode<Integer> firstHead = firstList.head; 
		ListNode<Integer> secondHead = secondList.head;
		BasicLinkedList<Integer> newList = 
			new BasicLinkedList<Integer>();
		
		// move smaller node into newList, and maintain its tail
		if (firstHead.getElement() <= secondHead.getElement()) {
			newList.head = firstHead;
			firstHead = firstHead.getNext();
		} else {
			newList.head = secondHead;
			secondHead = secondHead.getNext();
		}
		ListNode<Integer> newTail = newList.head; 
		
		// attach smaller node to newTail, i.e. to the end of newList
		while (firstHead != null && secondHead != null) {
			if (firstHead.getElement() <= secondHead.getElement()) {
				newTail.setNext(firstHead);
				firstHead = firstHead.getNext();
			} else {
				newTail.setNext(secondHead);
				secondHead = secondHead.getNext();
			}
			newTail = newTail.getNext();
		}
		
		// concatenate the non-empty list to the end of newList
		if (firstHead != null)
			newTail.setNext(firstHead);
		if (secondHead != null) 
			newTail.setNext(secondHead); 
		
		// perform cleanup
		firstList.head = null; 
		secondList.head = null;
		return newList;
	}
	
	public void logicalRemove(ListNode<E> target) {
		target.setElement(target.getNext().getElement()); // overwrite target
		target.setNext(target.getNext().getNext()); // delete next node
		num_nodes--; // often neglected
	}
	
	// Data attributes
	protected ListNode <E> head = null;
	protected int num_nodes = 0;

	// Return true if list is empty; otherwise return false.
	public boolean isEmpty() { 
		return (num_nodes == 0); 
	}

	// Return number of nodes in list.
	public int size() { 
		return num_nodes; 
	}

	// Return value in the first node.
	public E getFirst() throws NoSuchElementException {
		if (head == null) 
			throw new NoSuchElementException("can't get from an empty list");
		else return head.getElement();
	}

	// Return true if list contains item, otherwise return false.
	public boolean contains(E item) {
		for (ListNode <E> n = head; n != null; n = n.getNext())
			if (n.getElement().equals(item)) return true;

		return false;
	}

	// Add item to front of list.
	public void addFirst(E item) {
		head = new ListNode <E> (item, head);
		num_nodes++;
	}

	// Remove first node of list.
	public E removeFirst() throws NoSuchElementException {
		ListNode <E> ln;
		if (head == null) 
			throw new NoSuchElementException("can't remove from an empty list");
		else { 
			ln = head;
			head = head.getNext();
			num_nodes--;
			return ln.getElement();
		}
	}

	// Print values of nodes in list.
	public void print() throws NoSuchElementException {
		if (head == null)
			throw new NoSuchElementException("Nothing to print...");

		ListNode <E> ln = head;
		System.out.print("List is: " + ln.getElement());
		for (int i=1; i < num_nodes; i++) {
			ln = ln.getNext();
			System.out.print(", " + ln.getElement());
		}
		System.out.println(".");
	}
}