public class RemoveNthFromEnd {
	
	public class ListNode {
		int val;
		ListNode next;
		ListNode(int x) {
			val = x;
		    next = null;
		}
	}
	/*//先算节点个数count，把顺数第count-n个数的next改为第count-n-2个数
	public ListNode removeNthFromEnd(ListNode head, int n) {
		
		int count = 1;
		ListNode temp = head;
		while(temp.next != null){
			count++;
			temp = temp.next;
		}
		int i = count-n;
		if(i == 0){
			return head.next;
		}
		temp = head;
		while(i > 1){
			temp = temp.next;
			i--;
		}
		temp.next = temp.next.next;
		
		return head;
    }*/
	//题目要求最好一遍遍历，那就靠数学的巧妙的，两指针，first先走n步，
	//再first和second同时走，直到first的next是空，就把second的next改为next的next
	public ListNode removeNthFromEnd(ListNode head, int n) {
		
		ListNode first = head, second = head;
		for(int i=n; i>0; i--){
			first = head.next;
		}
		if(first == null){
			return first;
		}
		while(first.next != null){
			first = first.next;
			second = second.next;
		}
		second.next = second.next.next;
		
		return head;
    }
}