广州 营销型网站建设/百度的网址

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

示例 ：

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

解题思路：

使用一趟扫描实现。这里就是双指针的经典应用。如果要删除倒数第n个节点，让fast移动x步，然后让fast和slow同时移动，直到fast指向链表末尾的下一个结点nullptr，这时候大家才会停下来。

那么问题来了，应该是先让fast指针移动多少步才合理呢。

首先，我们使用虚拟头结点，这样方便处理删除实际头结点的逻辑。

那么，快慢指针都是从虚拟头结点出发的。使用上图的例子，也添加虚拟头结点，那一共有5个结点（虚拟头结点不算是结点）。要让fast指针走到nullptr,那需要走6(5+1)步。而要慢指针走到被删除的结点的前一结点停下来，那需要slow指针走3（5-2）步。

一般化：

那么，设一共有k个结点，那fast指针走到nullptr,那需要走k+1步。slow指针要走到被删除的结点的前一结点，需要走(k-n)步。

一开始，假设fast指针先走x步，接着fast,slow指针同时走，而slow指针走（k-n）步，就停下来，而fast指针也就跟着走(k-n)步就走到了nullptr。

所以k+1=(k-n)+x; x=n+1;

所以fast指针需要先走n+1步。

理解了这个，代码就好写了。

代码：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {auto dumyhead=new ListNode(0,head);auto fast=dumyhead;for(int i=0;i<=n;++i)fast=fast->next;auto slow=dumyhead;while(fast){fast=fast->next;slow=slow->next;}//这里没有写到delete 结点slow->next=slow->next->next;return dumyhead->next;}
};

相关文章：