来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

例如：给定一个链表: 1->2->3->4->5, 和 n = 2。当删除了倒数第二个节点后，链表变为 1->2->3->5。

说明：

给定的 n 保证是有效的。

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

二、题解

使用快慢指针，快指针先走n步，满指针再走，当快指针为空的时候满指针就是倒数第n个节点。

和《剑指offer》面试题22：链表中的倒数第k个节点类似，知识剑指offer中是返回倒数第n个节点，这道题目是删除倒数第n各节点，多了个删除操作。

三、代码

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *prev, *fast, *slow;
        prev = nullptr;
        fast = head;
        slow = head;

        // 快指针先走n步
        while (fast && n--)
            fast = fast->next;

        // n大于链表长度，直接返回head
        if (!fast && n > 0)
            return head;

        // 遍历快慢指针，并备份慢指针
        while (fast != nullptr) {
            prev = slow;
            fast = fast->next;
            slow = slow->next;
        }

        // 删除节点，注意删除的节点可能是链表收尾节点
        if (prev) {
            // 如果删除的是最后一个节点，slow为空
            prev->next = slow ? slow->next : nullptr;
            return head;
        } else {
            // 删除的首节点，返回首节点的下一个节点
            return head->next;
        }
    }
};