Remove Nth Node From End of List

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.

题目的要求是给定一个链表和一个整数n，从反方向数删除第n个节点。解决这道题目我们用双指针。根据题意我们分析，链表的头结点可能会被删除，因此我们要用一个辅助节点helper来记录链表的头结点。设定两个指针都指向helper，首先让fast指针移动n步，然后fast指针和slow指针同时移动，直到fast指针为空，此时slow的下一个节点恰好为从后面数第n个节点。代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode helper = new ListNode(0);
        helper.next = head;
        ListNode fast = helper;
        ListNode slow = helper;
        for(int i = 0; i < n; i++) 
            fast = fast.next;
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return helper.next;
    }
}