题目：
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<n;i++)
{
if(fast.next!=null)
{
fast=fast.next;
}
}
/**
* 让fast节点和head节点一起走
* fast结束时，head离结束还有n个节点
* 此时head.next就是倒数第n个节点
* */
while(fast.next!=null)
{
fast=fast.next;
head=head.next;
}
head.next=head.next.next;
return fakeHead.next;
}
}
/**
* Definition for singly-linked list.
*/
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
@Override
public String toString() {
return "ListNode [val=" + val + "]";
}
}
