【校招VIP】链表算法之快慢指针题型- 校招VIP

考点介绍：

链表是校招面试里手撕代码出现频度比较高的题型，三线和中小厂会考察简单的链表反转，大厂会进一步考察复杂度和双指针问题，比如中间元素、是否存在环等。

本期分享的链表算法之快慢指针题型，分为试题、文章以及视频三部分。

答案详情解析和文章内容可扫下方二维码或链接即可查看！

一、考点题目

1.一个长度为n的单向链表，用O(1) 空间复杂度来实现倒转输出，使用最低时间复杂度

解答：空间复杂度为O(1)，只能一次取一个结点，并把它的next结点指向第一个结点……

2. 找出单链表的中间元素，要求用时最少

解答：正常的话，需要先遍历一圈，得到链表长度。再从头遍历到1/2长度的位置……

3.判断单链表中是否有环，写出代码

解答：如果只用一个指针next的话，是不能知道到底有环造成一直循环还是链表长度很长造成的，而且循环了的话，程序没有终结态……

4.如果单链表中是有环，请找到环的入口点

解答：这道难属于难题。需要一点点的数学推导，不是很明白的同学，可以只记住结论……

（答案点击下方链接或者扫海报二维码查看哦）

二、考点文章

1.链表排序算法java实现（链表的快速排序、插入排序、归并排序）

链表的排序相对数组的排序更为复杂些，也是考察求职者是否真正理解了排序算法（而不是“死记硬背”）......

2.链表算法经典十题总结

链表的倒数第K个结点问题描述：输入一个链表，输出该链表中……

（扫下方海报二维码查看完整版）

三、考点视频

1.arrayList和linkedList的区别和扩容

本题是面试常考题之一，但是很多同学没有真实理解或使用过相应的类，只靠记忆。在面试的时候，容易被问住……