题意：给定一个链表，要求移除从尾部开始的第n个节点并返回链表头。

19. Remove Nth Node From End of List (opens new window)

比较简单的解法是先算出链表的长度，然后从头开始移动size-n个节点即可。但是这样会遍历两次链表，有没有可能只遍历一次？可以使用双指针a和b，a先移动n个节点，然后a和b同时移动，直到a到达尾部，这样b刚好停留在需要删除的节点。最后需要处理一下特殊情况，当size=n时，a指针刚好指向null，这时有两种情况，size=1，返回null；size>1，返回head.next。第一种情况head.next也是null，所以返回head.next即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 双指针，第一个指针先移动n次，然后第二个指针和第一个指针一起移动，直到第一个指针到底
        // 第二个指针的位置刚好停留在要删除的节点
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        if (first == null) {
            return head.next;
        }
        while (first.next != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return head;
    }
}