大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位同学放弃了大厂年包60w+的offer，考虑到稳定性和生活成本，最终选择去离家近的垄断性国企。从评论区得知楼主要去的是珠三角电网，一位刚从电网离职的同学劝楼主不要去电网，电网加班也很多，后面会后悔的。不过看起来楼主已经做过充分对比了，楼主认为后不后悔跟选择哪个没关系，只要在这两条路中做选择，不管选哪个都会后悔，自己目前选择的是一种生活而不是一份工作。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道高频面试题「删除链表的倒数第 N 个结点」。
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
举个例子：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路解析
根据题目描述中的例子，如果要删除倒数第2个节点，那么需要拿到指向倒数第3个节点的指针pre。执行pre->next = pre->next->next，即可删除倒数第2个节点。
寻找倒数第三个节点的算法如下：
创建一个虚拟头节点 tempHead，tempHead->next = head，定义两个指针left = tempHead，right = head。right先走2步，然后left和right同时往前走，直到right指向空节点，这个时候left指向的节点就是倒数第3个节点。
有些同学会疑惑，怎么知道right要让left领先几步？这个时候我们可以倒推，根据例子在纸上画个简单的链表，让right指向最终的状态，最后一个节点的下一个节点，即NULL节点。left指向要删除节点的前一个节点，然后数一数有几个箭头，就让right领先left几步。
由简单的例子推广到要删除链表的倒数第n个节点，在创建虚拟头节点tempHead的情况下，left = tempHead 就可以先让right指针领先left指针 n + 1 步，如果一开始right指针指向head节点(即tempHead->next)，就需要先走n步。
为什么要创建一个虚拟头节点呢？增加了一个虚拟头节点边界情况都会包含在主逻辑中，整体的算法逻辑更清晰。如果不使用虚拟头节点，会增加一些边界情况的处理，有兴趣的同学可以尝试实现一下。增加虚拟头节点也属于处理一些链表题目的小技巧。
C++代码
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//创建虚拟节点
ListNode* tempHead = new ListNode(0, head);
ListNode* left = tempHead;
ListNode* right = head;
//right先走n步
while (n > 0 && right) {
right = right->next;
n -= 1;
}
while (right) {
left = left->next;
right = right->next;
}
//删除倒数第n个节点
ListNode* temp = left->next;
left->next = left->next->next;
delete temp;
return tempHead->next;
}
};
python代码
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 创建虚拟节点
tempHead = ListNode(0, head)
left = tempHead
right = head
# right先走n步
while n > 0 and right:
right = right.next
n -= 1
while right:
left = left.next
right = right.next
# 删除倒数第n个节点
temp = left.next
left.next = left.next.next
del temp
return tempHead.next
复杂度分析
时间复杂度： 只需要遍历一遍链表，所以时间复杂度为O(n)，其中n为链表的长度。
空间复杂度： 需要借助一个虚拟头节点，所以空间复杂度为O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
