大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位阿里的员工吐槽自己面试小红书的经历，早上投了简历下午就被拒了。他认为自己的履历还可以，985本科毕业，还有两年大厂工作经验，自认为能力也不错，绩效一直很好，很好奇小红书是怎样选人的。
评论区不少在大厂工作的脉友也跟着吐槽自己面试小红书的类似经历，很多都直接挂在简历筛选这一关。有些对小红书招聘套路比较熟悉的脉友说小红书比较看重工作内容的匹配度，带着代码或者带着方法论和阿里味过来最好了。还有一位小红书内部人士分享了hr视角，说是小红书的简历库全是985硕士和海外top100的海归，简历不过很正常。大家有类似胜券在握，却被意外刷简历的经历吗？
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道小红书的面试原题「环形链表 II」。
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
不允许修改 链表。
举个例子：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
思路解析
根据「LeetCode 141.环形链表」这道题中的思路，定义两个指针slow和fast，一开始两个指针均指向链表头节点head，slow每次移动一步，fast每次移动两步。如果链表存在环，快慢指针一定会在环中相遇。
假设链表环外部分的长度为X，环的周长为Y，相遇点距离环的入口长度为a。
那么在快慢指针相遇时快指针走的距离是慢指针走的距离的两倍，下面等式成立。
2(X + mY + a) = X + nY + a, n > m >= 0
其中m为慢指针在环内走的圈数，n为快指针在环内走的圈数。
简化后可得：
X = （n - 2m)Y - a, n > 2m >= 0
说明如果一个指针从链表头节点开始向后移动，另一个指针同时从当前相遇点开始移动，两个指针每次均移动一步，那么他们一定会在环的入口相遇。
所以在一开始快慢指针相遇的时候，我们就把快指针移到链表的头节点，然后缩小移动的步长为1，这样当两个指针再次相遇我们就获得了环形链表的入口节点。
下面我们给出c++和python的两种代码实现。
c++代码
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head)
return NULL;
ListNode* slow = head;
ListNode* fast = head;
//slow和fast先移动一次
if(head)
slow = slow->next;
if(slow)
fast = slow->next;
while(fast && fast->next && slow != fast)
{
slow = slow->next;
fast = fast->next->next;
}
//相遇了说明存在环
if(slow == fast)
{
//此后快指针从head开始每次移动一步
fast = head;
while(slow && fast && slow != fast)
{
slow = slow->next;
fast = fast->next;
}
//两个指针相遇的地方就是环的入口
if(slow == fast)
return slow;
}
return NULL;
}
};
python代码
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
slow = head
fast = head
# slow和fast先移动一次
if head:
slow = slow.next
if slow:
fast = slow.next
while fast and fast.next and slow != fast:
slow = slow.next
fast = fast.next.next
# 相遇了说明存在环
if slow == fast:
# 此后快指针从head开始每次移动一步
fast = head
while slow and fast and slow != fast:
slow = slow.next
fast = fast.next
# 两个指针相遇的地方就是环的入口
if slow == fast:
return slow
return None
复杂度分析
时间复杂度： 时间复杂度为O(n)，其中n为链表的长度。
空间复杂度： 只借助了两个指针，所以空间复杂度为O(1)。
今天的分享就到这里，希望大家有所收获！
