题目：

Given a linked list, remove the nth node from the end of list and return its head.For example,  Given linked list: 1->2->3->4->5, and n = 2.  After removing the second node from the end, the linked list becomes 1->2->3->5.Note:  Given n will always be valid.  Try to do this in one pass.

 

　　

 

主要思想：

首先，为链表添加头指针，添加一个头指针fakeHead，fakeHead.next=head,然后head=fakeHead。结果如下图所示：

 

然后，创建一个走的快的指针fast，指向head.next。结果如下图所示：

 

此时，我们以n=2为例，说明运行过程。让fast指针往前走n=2个节点。结果如下图所示：

最后，让head和fast指针一起往前走，当fast指针走到最后时，head指针后面还有n个节点未走完。结果如下图所示：

此时，head.next就是倒数第n=2个节点。

 

java代码如下：

public class RemoveNthNodeFromEndofList {	public static void main(String[] args) {		ListNode ln1= new ListNode(1);		ListNode ln2= new ListNode(2);		ln1.next=ln2;		ln2.next=null;		System.out.println(removeNthFromEnd(ln1,1).toString());	}	public static ListNode removeNthFromEnd(ListNode head, int n) {		ListNode fakeHead= new ListNode(-1);//创建一个虚拟的头结点		fakeHead.next = head;		head=fakeHead;//为head添加头节点		/**		 * 创建一个走的快的指针，比head指针快n个节点		 * */		ListNode fast=head;		for(int i=0;i