题目描述

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

例如：

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

解题思路

我们可以使用双指针的方法来解决这个问题。主要思路是使用两个指针fsat和slow，先让fsat指针移动n+1步，然后两个指针同时移动，当fast到达链表末尾时，slow正好指向倒数第N+1个节点，这时删除倒数第N个节点即可。

具体步骤如下：

1. 初始化一个虚拟头节点dummyNode，指向链表的头节点，这样可以处理删除头节点的情况。
2. 初始化两个指针fast和slow，都指向虚拟头节点。
3. 移动fast指针，先向前移动n+1步。
4. 同时移动fast和slow指针，直到fsat到达链表末尾。
5. 此时，slow指向倒数第N+1个节点，删除slow的下一个节点。
6. 返回虚拟头节点的下一个节点作为新的头节点。

算法实现

C++实现

/*** 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) {ListNode*dummyNode=new ListNode(0);dummyNode->next=head;ListNode*fast=dummyNode;ListNode*slow=dummyNode;while(n--&&fast!=nullptr){fast=fast->next;}while(fast->next!=nullptr){slow=slow->next;fast=fast->next;}ListNode*tmp=slow->next;slow->next=slow->next->next;delete tmp;tmp=nullptr;return dummyNode->next;}
};

复杂度分析

• 时间复杂度：O(n)，其中n是链表的长度。两个指针遍历链表需要两次遍历，一次获取删除节点的位置，另一次执行删除操作。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

通过本文，我们介绍了一种简单而有效的删除链表倒数第N个节点的方法。使用双指针技巧，我们能够在一次遍历中完成删除操作，并避免了需要使用额外空间的额外临时数组。这种方法不仅时间复杂度低，而且代码简洁，适用于大规模链表的操作。

希望这篇博客能对你有所帮助。如果有任何问题，欢迎随时讨论与交流。