SplitLinkedSturcture.java

static public MyLinkedSort[] split(MyLinkedSort l){ // TODO
      // parameter is a List
	  // it returns an array of size 2
	  // the 0th element is the left list
	  // the first element is the right list
		MyLinkedSort left = l;
		MyLinkedSort right = l;
		
		Node leftFirst = left.first;
		Node rightFirst = right.first;
		
		int size = l.N;
		
		Node cycleLeft = new Node();
		Node cycleRight = new Node();
		cycleLeft = leftFirst;
		cycleRight = rightFirst;
		int i = 1;
		while(i < size/2) {
			cycleLeft = cycleLeft.next;
			cycleRight = cycleRight.next;
			i++;
		}
		rightFirst = cycleRight.next;
		cycleLeft.next = null;
		
		left.first = leftFirst;
		left.N = size/2;
		right.first = rightFirst;
		right.N = size - left.N;
		
		MyLinkedSort[] splited = {left, right};
		return splited;
	  }