考点介绍：
链表是校招面试里手撕代码出现频度比较高的题型，三线和中小厂会考察简单的链表反转，大厂会进一步考察复杂度和双指针问题，比如中间元素、是否存在环等。
一、考点题目
1.一个长度为n的单向链表，用O(1) 空间复杂度来实现倒转输出，使用最低时间复杂度
解答：单向链表，直接设结点 Node head； 要倒转就需要重置链接，设记忆结点 Node p
空间复杂度为O(1) ，就是不能使用……
2.找出单链表的中间元素，要求用时最少
解答：最简单实现，先遍历一遍链表，取得长度n；再遍历一遍，取n/2的位置的结点……
3.单链表中是否有环，写出代码
解答：一个指针只能遍历，没有办法做出判断；尝试两个结点，两个结点通常是slow走一步，fast走两步……
4.如果单链表中是有环，请找到环的入口点
解答：思路
这是【单链表中是否有环，写出代码】的扩展题，可以划分到面试中难度最大的那一档中
找环的入口点，就是找到入口点是链表的第几个结点，设这个结点q是……
5.已知 pPre 为指向链表中某结点的指针， pNew 是指向新结点的指针，以下哪段伪码算法是将一个新结点插入到链表中 pPre 所指向结点的后面？
A.pPre->link = pNew; pNew = null
B.pPre->link = pNew->link; pNew->link = null
C.pNew->link = pPre->link; pPre->link = pNew
D.pNew->link = pPre->link; pPre->link = null
解答：正确答案是 C，首先将旧结点的指针域(即pPre->Link,它存放着接下来的那个结点的地址)赋值给新结点的指针域（pNew- >Link）……
二、考点文章
1.那些前端用js手搓出来的算法与数据结构（一）链表篇
链表类
前序遍历判断回文链表
利用链表的后续遍历，使用函数调用栈作为后序遍历栈，来判断是否回文
2.前端必备算法－－链表
链表是一种物理存储单元上非连续、非顺序的存储结构。链表由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是......
3.常见算法总结 - 链表篇
本文总结了常见高频的关于链表的算法考察。
1.如何找到链表的中间元素？
我们可以采用快慢指针的思想，使用步长为1的慢指针和......
三、考点视频
分别使用冒泡和快速排序
本题重点在于考查数据结构的排序算法，小讲分别使用了简单的冒泡排序和复杂的快速排序，从思路到实现......
更多资讯可搜索校招VIP小程序查看哦！
移动端：https://m.xiaozhao.vip/dTopic/detail/1136
PC端：https://xiaozhao.vip/dTopic/detail/1136
