力扣19.删除链表的倒数第N个节点

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

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

示例 1：

1 2	输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

1 2	输入：head = [1], n = 1 输出：[]

示例 3：

1 2	输入：head = [1,2], n = 1 输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list

思路

可以通过遍历计算链表长度得到 $L$ 然后第二次找到 $L-n+1$ 进行删除，也可以通过双指针的方法使快指针领先慢指针 $n$ ，当快指针位于链表尾部时慢指针即处于要删除的节点，还可以通过栈（先进后出）来取得倒数 $n$ 个节点。这里提供一种递归的方法，类似于栈进行处理。

当处于尾节点时，返回1，判断当处于 $n+1$ 时返回节点（需要删除的节点的上一个），其余进行++操作。由于对于头节点需要分开处理，这里采用虚头节点( $dummy$ 节点）进行统一处理。

实现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //如果链表空直接返回
        if(!head)   return nullptr;
        //创建哨兵节点
        ListNode* dummyHead = new ListNode(0, head);
        //声明用于计数以及储存节点的指针
        int count = 0;
        ListNode* pred;
        //递归寻找节点
        removeCount(dummyHead, n, count, pred);
        //进行删除
        ListNode* current = pred->next;
        pred->next = current->next;
        delete current;
        return dummyHead->next;
    }

    void removeCount(ListNode* head, int n, int& count, ListNode*& pred)
    {
        //如果为尾节点就把count记为1
        if(head->next == nullptr)
        {
            count = 1;
            return;
        }
        //递归调用
        removeCount(head->next, n, count, pred);
        //count计数++
        count++;
        //找到节点直接保存
        if(count == n + 1)  pred = head;
    }
};