solution.md

# 删除链表的倒数第 N 个结点

<p>给你一个链表，删除链表的倒数第 <code>n</code><em> </em>个结点，并且返回链表的头结点。</p><p><strong>进阶：</strong>你能尝试使用一趟扫描实现吗？</p><p><strong>示例 1：</strong></p><img alt="" src="https://img-blog.csdnimg.cn/img_convert/3ab1d7132da7283b4578c8df78c8fb67.png#pic_center" /><pre><strong>输入：</strong>head = [1,2,3,4,5], n = 2<strong><br />输出：</strong>[1,2,3,5]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>head = [1], n = 1<strong><br />输出：</strong>[]</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>head = [1,2], n = 1<strong><br />输出：</strong>[1]</pre><p><strong>提示：</strong></p><ul>	<li>链表中结点的数目为 <code>sz</code></li>	<li><code>1 <= sz <= 30</code></li>	<li><code>0 <= Node.val <= 100</code></li>	<li><code>1 <= n <= sz</code></li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode() : val(0), next(nullptr){};
    ListNode(int x) : val(x), next(nullptr){};
    ListNode(int x, ListNode *next) : val(x), next(next){};
};
```

### after

```c
int main()
{
    Solution sol;
    int n = 2;
    ListNode *L1 = new ListNode();
    ListNode *l11 = new ListNode(1);
    ListNode *l12 = new ListNode(2);
    ListNode *l13 = new ListNode(3);
    ListNode *l14 = new ListNode(4);
    ListNode *l15 = new ListNode(5);

    L1->next = l11;
    l11->next = l12;
    l12->next = l13;
    l13->next = l14;
    l14->next = l15;

    ListNode *res = new ListNode();

    res = sol.removeNthFromEnd(L1, n);

    ListNode *p = res->next;

    while (p != NULL)
    {
        cout << p->val << " ";
        p = p->next;
    }

    return 0;
}
```

## 答案

```c

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {

        if (head->next == NULL)
        {
            delete head;
            return NULL;
        }

        ListNode *fast = head;
        ListNode *slow = head;
        for (int i = 0; i < n; ++i)
            fast = fast->next;

        if (fast == NULL)
        {
            ListNode *temp = head->next;
            head->val = temp->val;
            head->next = temp->next;
            return head;
        }

        while (fast->next != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        slow = slow->next;
        return head;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {

        auto dummy = new ListNode(0);
        dummy->next = head;

        auto lst = head;
        int len = 0;

        while (lst != NULL)
        {
            ++len;
            lst = lst->next;
        }

        int target = len + 1 - n;

        lst = dummy;
        while (target > 1)
        {
            lst = lst->next;
            --target;
        }
        lst->next = lst->next->next;

        return dummy->next;
    }
};
```

### B

```c
class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *h = new ListNode(0);
        h->next = head;
        ListNode *p = h;
        ListNode *k = h;
        if (head->next == NULL)
            return {};
        for (int i = 0; i <= n; i++)
        {
            k = k->next;
        }
        while (k)
        {
            p = p->next;
            k = k->next;
        }
        p->next = p->next->next;
        return h->next;
    }
};
```

### C

```c
class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        int count = 0;
        ListNode *p = head;
        while (p)
        {
            count++;
            p = p->next;
        }
        p = head;
        if (count == 1)
            return {};
        else if (count - n == 0)
            return head->next;
        else
        {
            for (int i = 1; i < count - n; i++)
            {
                p = p->next;
            }
            p->next = p->next->next;
        }
        return head;
    }
};
```