用两个速度不一样的指针从头遍历,如果存在环,则快的指针终将追上慢的指针!
bool CircleInList(Link* pHead)
{
if(pHead == NULL || pHead->next == NULL)//无节点或只有一个节点并且无自环
{
return (false);
}
if(pHead->next == pHead)//自环
{
return (true);
}
Link *pTemp1 = pHead;//step 1
Link *pTemp = pHead->next;//step 2
while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL)
{
pTemp1 = pTemp1->next;
pTemp = pTemp->next->next;
}
if(pTemp == pTemp1)
{
return (true);
}
return (false);
}
分享到:
相关推荐
供大家交流使用,欢迎大家交流指对。。。欢迎大家下载。。
主要介绍了python判断单向链表是否包括环,若包含则计算环入口的节点,结合实例形式分析了Python针对单向链表的遍历、判断相关算法原理与使用技巧,需要的朋友可以参考下
附件是使用双指针发判断链表有环的代码实现,在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步...
给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。
VC6.0下 用C语言实现单向链表的创建、插入,删除节点,和2个链表合并等操作
根据链表数据结构的知识,进行初步练习,从单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串四个题目着手,分别进行代码实现。 首先定义单链表类: # 结点类 class Node(object): def _...
在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔...在Main类中,我们创建了一个链表,并故意引入了一个环(最后一个节点指向第二个节点),然后调用hasCycle方法来判断链表是否有环,并打印出相应的结果。
从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item)...
算法提要:深度优先遍历过程中,访问某顶点后,该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边),则有环。 3.编程题: 建立无向图邻接表存储结构,输出深度和宽度优先...
1.判断链表是否存在环型链表问题:判断一个链表是否存在环,例如下面这个链表就存在一个环: 例如N1->N2->N3->N4->N5->N2就是一个有环的链表,环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1,p2。每次...
前端面试常考的要点数据结构链表单向链表判断环以及环入口双向链表循环链表各种树b+树b-树b*树红黑树二叉树满二叉树平衡二叉树哈夫曼树完全二叉树二叉查找树队列哈希
算法提要:深度优先遍历过程中,访问某顶点后,该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边),则有环。 3. 上机题 1. 编程题: 建立无向图邻接表存储结构,输出深度和...
算法提要:深度优先遍历过程中,访问某顶点后,该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边),则有环。 3. 编程题: 建立无向图邻接表存储结构,输出深度和宽度优先...
2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public ...
2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public LNode ...
CD108:反转部分单向链表 CD109:环形单链表的约瑟夫问题(进阶,CD110) CD111:判断一个链表是否为回文结构(时间复杂度O(N),空间复杂度O(N)) CD112:判断一个链表是否为回文结构(进阶,时间复杂度O(N),空间...
判断单向列表是否有环 206 翻转单向链表 237 删除链表元素 203 删除链表多个元素 206 翻转链表 141 环形链表 2021-05-15: 876 获取链表中间节点 20 判断括号是否成对 2021-05-16: 150后缀表达式 224基本计算器 856...
2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public LNode ...
循环链表和单向链表基本一致,差别仅在于算法中循环的条件不是结点的指针是否为空,而是他们的指针是否等于头指针, 循环链表最后一个结点的 link 指针不为 0 (NULL),而是指向了表的前端。 为简化操作,在循环链表...