摘要：继续链表算法有点恍恍惚惚。两个指针先后进入环里面，一个比另一个每次快一步，是不是一定会遇上。只是为了保证可以执行操作。反正走了步相遇，那么快的领先慢的步，正好是一圈的长度。所以如果快节点从头开始和慢节点以一样的一格一格跑，必在入口处相遇。
继续链表算法
有点恍恍惚惚。
题目描述：判断一个单链表是否有环
分析：还是通过快慢指针来解决，两个指针从头节点开始，慢指针每次向后移动一步，快指针每次向后移动两步，如果存在环，那么两个指针一定会在环内相遇。首先单链表有环是什么一种结构呢？ 小b这种结构么？ 因为只能是单方向的指引，所以应该是小b这种结构。两个指针先后进入环里面，一个比另一个每次快一步，是不是一定会遇上。是的。那么如果快两步呢？就是一个指针每次走3步，另一个每次走一步？相遇的话，快的那个是不是一定领先慢的那个若干个圈的长度？假设经过x步相遇，那么领先2x个节点。所以圈内节点数一定要是偶数才行？先想题目吧。
function linkedListWithCircle(head){
if(head==null||head.next==null) return false;
var fastNode = head;
var normalNode = head;
while(fastNode!=null&&fastNode.next!=null){//只是为了保证可以执行fastNode.next.next操作。避免null.next错误。
fastNode = fastNode.next.next;
normalNode = normalNode.next;
if(normalNode==fastNode) return true;
}
return false;
}
题目描述：判断单链表是否有环，如果有，找到环的入口点
分析：由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让 p2 回到链表的头部，重新走，每次步长不是走 2 了，而是走 1，那么当 p1 和 p2 再次相遇的时候，就是在环路的入口点。加深思考。
function findLoopPort(head){
if(head==null||head.next==null) return null;
var fastNode = head;
var normalNode = head;
var hasCircle = false;
while(fastNode != null&&fastNode.next != null){
fastNode = fastNode.next.next;
normalNode = normalNode.next;
if(normalNode == fastNode) {
hasCircle = true;
break;
}
}
if(!hasCircle) return null;//原本想return false，后来发现还是null好。
var fastNode = head;
while(fastNode != normalNode){
fastNode = fastNode.next;
normalNode = normalNode.next;
}
return fastNode;
}
想画个图来着。还是算了吧。反正走了x步相遇，那么快的领先慢的x步，正好是一圈的长度。
假设从头节点到圈的入口要走m步，那么慢节点在圈内走了x-m步，从相遇的节点到入口节点，差x-(x-m)=m步。
所以如果快节点从头开始和慢节点以一样的一格一格跑，必在入口处相遇。
还是画个图吧。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/90219.html
摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...
摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法为王。 想学好前端，先练好内功，...
摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法为王。想学好前端，先练好内功，内功不行，就...
摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。 本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...
摘要：因为是在已经分组排序过的基础上进行插入排序，所以效率高。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。形成左右两个分区，再递归按之前的步骤排序。 算法复杂度 不是科班生的我，第一次看见时间复杂度之类的名词表示很懵逼，所以就找了网上的资料补习了下： 时间复杂度：是指执行算法所需要的计算工作量 空间复杂度：是指算法在计算机内执行时所需存储空间的度量 排序算法稳定性： 假定在待...
摘要：栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构，比如下面介绍的二叉查找树。 前言 在过去的几年中，得益于Node.js的兴起，JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器，程序员发现他们需要更多传统语言（比如C++和Java）提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等），...
阅读 1683·2019-08-30 15:53
阅读 3005·2019-08-30 15:44
阅读 2674·2019-08-26 13:31
阅读 1840·2019-08-26 12:10
阅读 669·2019-08-26 11:01
阅读 1983·2019-08-23 15:32
阅读 1438·2019-08-23 13:43
阅读 2380·2019-08-23 11:58
