[链表] LeetCode 19. 删除链表的倒数第N个节点

[链表] LeetCode 19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

这里是简单版，只用找到倒数第n个结点 [链表] LeetCode 面试题22. 链表中倒数第k个节点

因为要删除倒数第n个结点，所以需要找到倒数第n-1个结点，因此让n+=1

方法就是设置一个慢指针一个快指针，先让快指针走n+1次，这样慢指针和快指针中间就相差n+1个结点，当快指针到达队尾时，慢指针到达倒数第n-1个结点

注意设置一个头节点，因为多走了一步，不设置头节点删除倒数第n个结点时会出错

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *q = new ListNode(0);
        q->next=head;
        ListNode *slow = q;
        ListNode *fast = q;
        for(int i = 0; i <= n; ++i)
            fast = fast->next;
        while(fast){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return q->next;
    }
};