19. Remove Nth Node From End of

题目描述：给链表，删除从尾部数的第n个元素。如：

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.

分析：一次遍历找出链表长度，再遍历一次删除第len - n的元素即可。但题目要求一次遍历解决，故设快慢指针，两指针间隔为n + 1，当快指针走到链表尾时删掉慢指针的next所指元素即可。时间复杂度O(n)，空间O(1)。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode l(-1);
        l.next = head;
        ListNode *p = &l, * q = &l;
        for ( int i = 0; i < n; i ++)
            q = q->next;                //先走n步
        while(q->next)
        {
            p = p->next;
            q = q->next;
        }
        ListNode *tmp = p->next;
        p->next = p->next->next;
        delete tmp;
        return l.next;
    }
};