博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
判断单链表是否有环
阅读量:4340 次
发布时间:2019-06-07

本文共 492 字,大约阅读时间需要 1 分钟。

问题:判断一个单链表中是否存在环

解:一个单链表中存在环,只能存在一种情形,就是尾部有环,不能在中间,否则就违背了单链表只有一个后继结点的原则。带环的单链表可以看成是一个单链表与一个循环链表的结合。判断单链表是否有环的常用方法是追逐法。设置两个指针p和q,p每一次向前走两步,q每一次向前走一步,如果有环,p一定能够追上q,如果无环,p的值先为NULL。

算法实现:

1 bool isCircleLink(linkNode *head) 2 { 3 if(head==null) 4 return false; 5 linkNode *p,*q; 6 p=q=head; 7 while(p!=null && p->next!=null) 8 { 9 p=p->next->next;10 q=q->next;11 if(p==q)12 break;13 }14 if(p==q && p!=null)15 return true;16 return false;17 }

 

转载于:https://www.cnblogs.com/cynthia-dcg/p/6008775.html

你可能感兴趣的文章
MySQL存储过程定时任务
查看>>
Python中and(逻辑与)计算法则
查看>>
POJ 3267 The Cow Lexicon(动态规划)
查看>>
设计原理+设计模式
查看>>
tomcat 7服务器跨域问题解决
查看>>
前台实现ajax 需注意的地方
查看>>
Jenkins安装配置
查看>>
个人工作总结05(第二阶段)
查看>>
Java clone() 浅拷贝 深拷贝
查看>>
深入理解Java虚拟机&运行时数据区
查看>>
02-环境搭建
查看>>
spring第二冲刺阶段第七天
查看>>
搜索框键盘抬起事件2
查看>>
阿里百川SDK初始化失败 错误码是203
查看>>
透析Java本质-谁创建了对象,this是什么
查看>>
BFS和DFS的java实现
查看>>
关于jquery中prev()和next()的用法
查看>>
一、 kettle开发、上线常见问题以及防错规范步骤
查看>>
eclipse没有server选项
查看>>
CRC码计算及校验原理的最通俗诠释
查看>>