java-60-在O(1)时间删除链表结点

public class DeleteNode_O1_Time {

	/**
	 * Q 60 在O(1)时间删除链表结点
	 * 给定链表的头指针和一个结点指针(!!)，在O(1)时间删除该结点
	 * 
	 * Assume the list is:
	 * head->...->nodeToDelete->mNode->nNode->...->tail
	 * you have already the point of 'nodeToDelete' in hand.So what you need to do is:
	 * 1.copy the data of 'mNode' to 'nodeToDelete'
	 * 2.nodeToDelete.next=nNode;
	 * However,when deleting the last node,you have to iterate from 'head'.No shortcut.
	 * 
	 * ---public static void deleteNode(Node head,Node nodeToDelete){
	 * cannot do it like that.Because you cannot set head=null to make 'list' empty.
	 * see 'class ParameterTransfer'
	 */
	public static void deleteNode(List list,Node nodeToDelete){
		Node head=list.head;
		if(head==null||nodeToDelete==null){
			return;
		}
		if(head.next==null&&nodeToDelete==head){//Only one node in list and you happen to delete the node.
			list.head=null;//head=null;-->wrong
			return;
		}
		Node node=head;
		if(node.next!=null&&nodeToDelete!=null){
			Node mNode=nodeToDelete.next;
			if(mNode!=null){
				Node nNode=mNode.next;
				nodeToDelete.data=mNode.data;
				nodeToDelete.next=nNode;
			}else {//'nodeToDelete' is the last Node.
				Node previous=node;
				while(node.next!=null){
					previous=node;
					node=node.next;
				}
				previous.next=null;
				return;
			}
			
		}
	}
	private static class List{
		private Node head;
		
		Node createList(int[] data){
			if(data==null||data.length==0){
				return null;
			}
			Node previous=null;
			for(int len=data.length,i=len-1;i>=0;i--){
				head=new Node(data[i]);
				head.next=previous;
				previous=head;
			}
			return head;
		}
		void printList(){
			Node node=head;//don't use 'head' immediately.It wastes my time to find the bug...
			while(node!=null){
				System.out.print(node.data+" ");
				node=node.next;
			}
			System.out.println();
		}
		Node getNodeAt(int pos){//starts from 0
			Node re=null;
			int index=0;
			Node node=head;
			while(node!=null){
				if(index==pos){
					return node;
				}
				node=node.next;
				index++;
			}
			return re;
		}
	}
	private static class Node{
		int data;
		Node next;
		Node(int data){
			this.data=data;
		}
	}
	
	public static void main(String[] args) {
		int[] data={0,1,2,3,4,5,6,7,8};
		List list=new List();
		list.createList(data);
		list.printList();
		
		Node nodeToDelete=list.getNodeAt(8);
		deleteNode(list,nodeToDelete);
		
		nodeToDelete=list.getNodeAt(3);
		deleteNode(list,nodeToDelete);
		
		nodeToDelete=list.getNodeAt(0);
		deleteNode(list,nodeToDelete);
		
		list.printList();//1 2 4 5 6 7
		
		list.createList(new int[]{1});
		deleteNode(list,list.getNodeAt(0));
		list.printList();//nothing.
		
	}
}

public class ParameterTransfer {

	/**
	 * 1.primitive type: pass by value
	 * 2.reference type: you can change the paremeter's status,but you cannot set it null.
	 */
	public static void main(String[] args) {
		ParameterTransfer p = new ParameterTransfer();
		TestData test = new TestData(1);
		p.setNull(test);
		System.out.println(test == null);// false--cannot set it null
		p.changeReference(test);
		System.out.println(test.i);//1--cannot change reference
		p.changeData(test);
		System.out.println(test.i);// 2--change its status
		
	}

	public void changeData(TestData test){
		test.i=2;
	}
	public void setNull(TestData test) {
		test = null;
		return;
	}
	
	public void changeReference(TestData test) {
		TestData test2=new TestData(2);
		test = test2;
		return;
	}
}

class TestData {
	int i;

	TestData(int i) {
		this.i = i;
	}
}