【校招VIP】前端算法考点之快慢指针题型

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

『前端算法考点之快慢指针题型』相关题目及解析内容可点击文章末尾链接查看！

一、考点题目

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的慢指针和......

三、考点视频

分别使用冒泡和快速排序

本题重点在于考查数据结构的排序算法，小讲分别使用了简单的冒泡排序和复杂的快速排序，从思路到实现......

『前端算法考点之快慢指针题型』相关题目及解析内容可点击下方链接查看：

前端算法考点之快慢指针题型-移动端链接
前端算法考点之快慢指针题型-PC端链接