【LeetCode】19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点（中等）

方法：快慢指针

思路

• 为了找到倒数第 n 个节点，我们应该先找到最后一个节点，然后从它开始往前数 n-1 个节点就是要删除的节点。

• 对于一般情况：设置 fast 和 slow 两个指针，分别指向「最后一个节点」和「要删除的节点的前一个节点」（这里是为了方便实现删除操作）。

  由于 fast 和 slow 最后指向的节点之间相距 n-1 步，因此我们先让 fast 走 n 步，同时需要保证 fast->next 不为空。

  接着令 fast 和 slow 同时前进，直到 fast 到达最后一个节点，此时 slow 指向 「要删除的节点的前一个节点」或者「要删除的节点」（当头节点需要删除的时候），修改 slow->next ，这样就删除了指定节点。

• 对于节点数为 1 的特殊情况，必然是删除这个唯一的节点，因此直接将 head 指向 nullptr。

代码

/*** 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->next) {head = nullptr;return head;}// 设置快慢指针ListNode *fast = head, *slow = head;// 在保证fast->next不为空的情况下，使fast比slow多走n步while(n >= 1 && fast->next) {fast = fast->next;n--;}// 当fast遍历到最后一个节点，说明slow已经走到倒数第n+1个节点// 这里将slow指向倒数第n+1个节点，是为了方便删除倒数第n个节点while(fast->next) {slow = slow->next;fast = fast->next;}// 当倒数第n个节点是头节点，特殊处理if(slow == head && n > 0) head = slow->next;// 否则删除第n个节点else slow->next = slow->next->next;return head;}
};