题目内容

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

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

题解

本题是一个链表的问题，这类题目建议大家多画图，用图辅助理解效果最好。

首先，还是跟之前一样，强调一下虚拟头结点的重要性。在链表求解的过程中，引入虚拟头结点之后，我们就可以将head指针和其他链表的其他节点一样统一处理，这样就避免了head指针的特殊性，我们处理起来更舒服，因此强烈建议在处理链表问题时，一定要创建一个虚拟头结点，然后让其指向head。

好了，看题，有如下思路：

1、因为要求倒数第n个点，因此链表的长度是一定要知道的，所以我们需要构建一个循环，把链表的长度求出来。

2、假设求出来链表的长度为N，那么倒数第n个点，其实就是正数第N-n+1个点。（公式为：target = length - 倒数第几 +1）

3、由于本题是一个单链表，所以想要删除一个节点，其实就是将要删除的节点的上一个节点的next指针指向要删除节点的下一个节点即可，用图表示如下：

4、倒数第n个节点的上一个节点就是倒数第n+1个节点，对应正数第N-(n+1)+1，即N-n个点。

具体，请看代码实现就好了。

代码

/**
 * 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) {
        auto dummy = new ListNode(-1);//创建虚拟头结点，里面的val随便设置，算法中不需要用。
        dummy -> next = head;//设置虚拟头结点指向head

        int length = 0;
        auto t = dummy;
        while(t){
          	//求出链表长度
            t = t -> next;
            length++;
        }
				
      	//开始进行删除操作
        t = dummy;
        //倒数第n+1个点就是正数第length-(k+1)+1=length-k个点。
        for(int i = 0;i < length - n - 1; i++) t = t ->next;
        t->next = t->next->next;

        return dummy->next;
    }
};