如何判断链表有没有环,环的大小?环的切入点在哪里以及链表的长度(分别用javascrip和Java代码实现)_senwei.zhang的博客-程序员秘密

技术标签: Coding  切入点  JavaScript  链表    

<script type="text/javascript">
function Node(n,next){
this.n=n;
this.next = next;
}

//
var node= new Node(1,null);
var linked = node;
for(var i=2;i<8;i++){
var temp = new Node(i,null);
node.next = temp;
node = node.next;
}
//形成链表,链表最后一个指向第三个
node.next = linked.next.next;
node = linked;
//验证是否成环
/*for(var i=0;i<25;i++){
document.write(node.n + "<br>");
node= node.next;
}*/
//如何判断有环,定义两个node,一个块,一个慢,看是否相遇
//让node1和node2同时从起点跑,node2的速度是node1的两倍
var node1 = linked;
var node2 = linked;

//看是否相遇
//设置一个标志flag初始值为false
var flag = false;
for(;(!(node1==node2))||(node1==node2&&node1==linked);){
document.write("循环进来了!"+ "<br>");
if(node2==null||node2.next==null){
//如果链表没环,让false赋值为true
flag = true;
break;
}
node1 = node1.next;
node2 = node2.next.next;
document.write(node1.n  + ":"+ node2.n+"<br>");
}
if(flag==true){
document.write("此链表没有环" + "<br>");
}
if(flag == false){
document.write("此链表有环" + "<br>");
}

//环的大小,让node1和node2接着走,再次相遇即是环的大小
var count=0;
for(;;){
node1=node1.next;
node2 = node2.next.next;
count++;
if(node1==node2){
break;
}
}
document.write("环的大小为:" +count +  "<br>");

//求环的切入点:慢的回到原点,快的原地跑,再次相遇的地方即是切入点
node1=linked;
for(;!(node1==node2);){
node1=node1.next;
node2=node2.next;

}
document.write("环的切入点" + node1.n+"<br>");
//求链表的大小,环的长度加上从头跑到切入点的长度即是链表的长度
node1=linked;
for(;!(node1===node2);){
node1 = node1.next;
count++;
}
document.write("链表的长度为:" + count);

</script>

用Java代码实现:


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/SoWhatWorld/article/details/77428454

智能推荐

《古月ROS探索总结》学习笔记2_宗而研之的博客-程序员秘密

转自:古月博客 http://blog.csdn.net/hcx25909/article/details/8795043

ext 级联_zyuanq的博客-程序员秘密

[code=&quot;js&quot;]var storeDepart=new Ext.data.JsonStore({ autoLoad : true, url:'deptList.action', root: 'data', fields : ['value','name']});var storeRUser=new ...

BRCC 编译错误:exited with code 1_zxm8513的博客-程序员秘密

brcc32commandlinefor"Project1.vrc"c:\programfiles\embarcadero\radstudio\9.0\bin\cgrc.exe-c65001"Project1.vrc"-foProject1.res[BRCC32Error]"brcc32"exitedwithcode1.解决办法:打开Project&gt;Options&gt;Application&gt;Appearance后再点“OK”按钮后,这下编译通过...

PyVim_weixin_30325971的博客-程序员秘密

PyVim主要用于连接到 Service Instanceimport atexitfrom pyVim import connect// Connect to ServerIf args.disable_ssl_verification: //no check SSL certification service_instance=connect...

Lisp的本质_圆月弯刀丶的博客-程序员秘密

Lisp的本质(The Nature of Lisp) 作者 Slava Akhmechet 译者 Alec Jang 出处: http://www.defmacro.org/ramblings/lisp.html简介最初在web的某些角落偶然看到有人赞美Lisp时, 我那时已经是一个颇有经验的程序员。在我的履历上, 掌握的语言范围相当广泛, 象C++,...

vue项目搭建(完整步骤)_vue 搭建项目_泪的结晶的博客-程序员秘密

一、安装node环境  1、下载地址为:https://nodejs.org/en/  2、检查是否安装成功:如果输出版本号,说明我们安装node环境成功    3、为了提高我们的效率,可以使用淘宝的镜像:http://npm.taobao.org/  输入:npm install -g cnpm –registry=https://registry.npm.taobao.org,即可安装npm镜像,以后再用到npm的地方直接用cnpm来代替就好了。    检查是否安装成功:

随便推点

三次软考高级经验总结:换位思考,多练习_hb15302782362的博客-程序员秘密

大家好,我是弘博软考的一名学员-黄英杰,一共参加了三次软考考试,终于在第三次的时候通过了,总算是到了软考总结的时候,今天就说说每次的软考的情况吧,希望对正在备考的你有所帮助。第一次软考&lt;一&gt;简述第一次软考是2019年下半年,是在通过了PMP后,想趁热打铁,把软考也通过了,结果论文和案例分析这两个板块挂了。案例失败的原因是,时间没有把握好,最后一题就是《汪博士解读PMP考试第5版》的44页,项目经理的权利,很简单的题目,前面两道题拖拉时间,最后一题未完成。论文挂了的原因是,没有花时

iOS点击空白处或点击背景收起键盘_troytan7的博客-程序员秘密

在viewDidLoad中添加手势- (void)viewDidLoad{[super viewDidLoad];//添加手势UITapGestureRecognizer *tap1 = [[UITapGestureRecognizer alloc] initWithTarget:self action:@selector(viewTapped:)];tap1.cancelsTo

D. Gargari and Permutations CodeForces - 463D (dp求多个数组的最长公共子序列)_我不管这题我就是不会做的博客-程序员秘密

题目链接:http://codeforces.com/problemset/problem/463/D题目大意:       给k个数组,每个数组都是1-n的排列,求k个数组的最长公共子序列。 1&amp;lt;=n&amp;lt;=1000   2&amp;lt;=k&amp;lt;=5题目思路:       从第一个数组入手,最长公共子序列一定存在于第一个数组中,那么对于有一对&amp;lt; i , j &amp;gt; ...

《Java 多线程编程核心技术》笔记——第2章 对象及变量的并发访问(四)_bm1998的博客-程序员秘密

2.3 volatile 关键字关键字 volatile 的主要作用是使变量在多个线程间可见。2.3.1 同步死循环创建一个公共类public class Service1 { private boolean isContinuePrint = true; public boolean isContinuePrint() { return isContinuePrint; } public void setContinuePrint(boole

linux系统下的打印机驱动下载,foo2zjs linux环境下打印机驱动源代码 - 下载 - 搜珍网..._每天开心的进步的博客-程序员秘密

文件名大小更新时间foo2zjs/foo2zjs/align.psfoo2zjs/foo2zjs/arm2hpdl.1infoo2zjs/foo2zjs/arm2hpdl.cfoo2zjs/foo2zjs/c5200mono.prnfoo2zjs/foo2zjs/ChangeLogfoo2zjs/foo2zjs/COPYINGfoo2zjs/foo2zjs/crd/qpdl/black-text....

推荐文章

热门文章

相关标签