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

给你一个链表，删除链表的倒数第 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

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

首先最简单的思路跟我们上一期内容的第一种解法类似删除链表中间节点，利用两次遍历循环链表，第一次遍历统计链表节点个数，第二次遍历利用index去找倒数第k个节点。思路如下

上述思想需要两次遍历链表，代码实现：

SListNode* removeNthFromEnd(SListNode* phead, int n){if (phead == NULL){return phead;}int count = 0;int index = 0;SListNode* Cur = phead;while(Cur){count++;Cur = Cur->next;};printf("%d\n",count);int target = count-n;printf("%d\n",target);if(target == 0){SListNode* del = phead;phead = phead->next;free(del);return phead;}else{Cur = phead;SListNode* Prev = NULL;while(Cur){index++;Prev = Cur;Cur = Cur->next;if(index == target){Prev->next = Cur->next;free(Cur);return phead;}};return phead;}
}

该算法需要两次遍历链表，如果我们只想遍历一次链表呢？这里不得不考虑使用我们的”双指针思想“，快慢指针，类似的题目包括 链表的中间节点，合并两个有序数组，删除有序数组中的重复项 移除元素,这道题的算法思想如下：

这里有两个需要注意的，1.当我们的链表只有一个元素，且正好我们正好删除头元素。

2. 当我们链表总共有n个元素，此时要删除的正好是第n个元素，也就是头元素。

算法代码实现：

SListNode* removeNthFromEnd(SListNode* phead, int n){if(phead == NULL){return phead;}//链表只有一个元素，且是我们要删除的元素。if(phead->next == NULL && n == 1){phead = NULL;return phead;}SListNode* Fast = phead;SListNode* Slow = phead;int count =0;while (Fast->next){if(count >= n){Slow = Slow->next; }Fast = (Fast->next);count++;}//循环结束后，发现我们要删除的是头元素。if(count == n-1){SListNode* del= phead;phead = phead->next;free(del);}else{SListNode* del= Slow->next;Slow->next = (Slow->next->next);free(del);}return phead;
}

这里我们的代码有些冗余对于头指针的处理，我们可以引入一个哑巴指针用于处理头节点，也就是新增一个节点指向我们的头指针！此时的fast，slow指针就是从哑巴指针开始遍历的

代码实现：

SListNode* removeNthFromEnd(SListNode* phead, int n){if(phead == NULL){return phead;}SListNode Dummy;Dummy.next = phead;SListNode* Fast = &Dummy;SListNode* Slow = &Dummy;int count = 0;for(int i =0;i<n;i++){Fast = Fast->next;}while (Fast->next){Fast = Fast->next;Slow = Slow->next;}SListNode* Del = Slow->next;Slow->next = Del->next;free(Del);return  Dummy.next;
}

这里面，我们要新建一个头节点，将其指向我们原来的头节点！

本期内容分享到此，谢谢大家！