字节后端一面

字节一面一上来就八股框框问,难绷,聊了四十分钟才开始手撕,我这边todesk看到直接开始写,先思路,再代码再注释,最后复杂度分析,一套流程下来也就十来分钟,没难度,简单说下面试手撕

使用两个指针,快指针先移动k步,然后快慢指针同时移动,当快指针到达链表末尾时,慢指针正好指向倒数第k个节点。

算法选择:双指针法。快指针先移动k步,如果快指针在移动过程中变为null,说明k大于链表长度,返回null。然后同时移动快慢指针,直到快指针到达链表末尾,此时慢指针指向的节点即为所求。

复杂度分析:时间复杂度为O(n),其中n是链表的长度,因为我们只遍历了一次链表。空间复杂度为O(1),只使用了两个指针。

最后面试官并没有追问思路什么的,一般手撕之后都会问一嘴代码的大概思路细节什么的,不过也顺利通过了,没什么问题,字节手撕题目不全是hot100,自己老老实实写肯定是有难度的,写不出来基本也是无缘了

全部评论

相关推荐

09-16 21:40
已编辑
浙江工业大学 Java
查看20道真题和解析
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务