大家好,我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位刚毕业就入职比亚迪的同学反思了自己为啥工作一年就决定离开,他从下面几点做了反思。
现实与想象的极度反差,抱着养老躺平的心态来的,进来才发现是自己太天真的,根本不适合躺平。 公司奖惩制度只看到了惩,随时看到各种通报批评,一级二级处罚只是为了降本直接绩效打折,对员工的没有关怀,直接搬进还没有装修好的新办公楼,戴着口罩、防毒面具办公,让人没有归属感。 流程层层审批,效率低下,大部分时间都在写文件,执行流程。
评论区有比亚迪的员工补充道,每天还有开不完的毫无意义的会议。一位刚拿了比亚迪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 ,年度会员有效期比官网多俩月,季度会员有效期比官网多两个星期,还有专属福利,需要的读者朋友可以找我了解。
今天的分享就到这里,希望大家能有所收获!