我现在有点明白了。面试过程中，面试官有时会让我们手写代码。其实主要是考大家的基本功，也是通过大众熟悉的领域来考核的。大家的系统思考和应对思路。在上一篇文章中学习了基础数据结构：链表（singlelinkedlist）。接下来我会从leetcode中选出几道有趣的算法题来和大家一起学习。如果是和链表中的相对位置有关，基本上通过引入双指针（快指针和慢指针），一次遍历就可以解决。1.检测单链表是否有环题目：如果给你一个指定的单链表，请判断是否有环。作为一个算法小白，看到这个题目，不假思索冒出的想法肯定是：引入一个HashSet，然后从头开始遍历单向链表，将每个元素存储在HashSet中。在遍历过程中，如果元素在HashSet中存在一个节点，则代表一个存储环。温馨提示：本文中的链表使用的是作者上面手写的链表。代码实现如下：在算法领域，通常有两个维度来评价一个算法的优劣：时间复杂度和空间复杂度。时间复杂度：O(N)，因为需要遍历整个链表。随着链表数据的增长，遍历的次数也会增加。空间复杂度：O(N)，因为这里额外申请了一个空间来存放遍历的节点。进阶：能否优化上述算法，将空间复杂度优化到O(1)。业界有一个经典的算法，龟兔赛跑算法，主要用来检测链表中是否有环。它通常可以解决以下问题：检测链表中是否存在环。如果有环，则计算环的入口节点。如果有环，则计算环的长度，从网上获取。“龟兔赛跑”具体说明：龟兔赛跑算法原理：引入快慢两个指针，两个指针同时从链表的头节点开始遍历，快指针每次移动2，慢指针每次移动1步。如果链表存环，快指针最终会追上慢指针，也就是两个指针会重叠；那么我们就可以按照这个规则写出如下示例代码：是不是很优雅，只需要引入两个指针。龟兔算法原理2：慢指针和快指针第一次相遇后，如果需要入环，方法是：将慢指针移到队头，然后移到队头所在的点快慢指针第一次相遇就是环节点的入口。2.删除链表中的最后第n个节点。在没有理解“龟兔赛跑算法”之前，要删除最后的第n个节点，肯定会遍历一次链表得到链表的总长度，用len表示，然后再遍历，只遍历第二次需要遍历（len-n）个节点。但是在我们学习了龟兔赛跑算法之后，相信读者朋友们一定也能想到，引入两个指针只能遍历一次。具体解决方法是：引入两个指针，在初始状态执行Header节点，然后让一个指针移动n次，然后同时移动两个指针，直到第一个指针到达链表尾部，此时第二个指针为倒数第n个节点，沿着上图，当最先移动到队尾时，状态图如下：跟具体代码写法有关，最后如图上图，因为倒数第n个节点被删除，是单链表，所以通常需要先找到要删除的节点的前驱节点。从这点来看，上述结束条件选择第一种更为合适。接下来是基于上述思路的代码实现：代码解读如下：代码@1：只要当前节点不为空，就可以继续向后驱动，主要是保证在刚好有n个节点的情况下，可以驱动n次，也很容易理解。比如现在有一个三个节点的链表。如果要删除倒数第三个，其操作轨迹如下图所示：代码@2：如果i小于n，说明没有遍历n次，缺少元素，一个数组直接抛出越界异常。代码@3：表示正好遍历n次，如上图，直接删除头节点。代码@4：接下来，first和second指针同步前移。由于单链表删除一个节点，需要知道被删除节点的前驱节点，所以first指针指向尾节点（node.next==null，表示已经到了尾），如如下图所示：代码的解读到此结束，不得不佩服双指针的强大。3.找到链表的中间节点经过上面两道题的讲解和训练，相信读者朋友们已经看到了这道与链表域中位置相关的题，终极杀手：双指针。解题方法：在中间的位置，那么我们可以引入两个快慢指针，快指针是慢指针速度的两倍，这样当快指针走到链表尾部时，慢指针正好走在链表的中间件位置。
