`
zhu_jinlong
  • 浏览: 5083 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

判断单向链表中是否有环

 
阅读更多
用两个速度不一样的指针从头遍历,如果存在环,则快的指针终将追上慢的指针!

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); 
  }
分享到:
评论

相关推荐

    判断一个链表是否有环,并指出换的头结点(O(n)时间复杂度)

    供大家交流使用,欢迎大家交流指对。。。欢迎大家下载。。

    python判断单向链表是否包括环,若包含则计算环入口的节点实例分析

    主要介绍了python判断单向链表是否包括环,若包含则计算环入口的节点,结合实例形式分析了Python针对单向链表的遍历、判断相关算法原理与使用技巧,需要的朋友可以参考下

    双指针法判断链表有环-Java 版

    附件是使用双指针发判断链表有环的代码实现,在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔赛跑”算法,也称为快慢指针法。这种方法利用两个指针,一个每次走一步(称为慢指针),另一个每次走两步...

    编程判断两个链表是否相交

    给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。

    C语言实现单向链表的创建、插入,删除节点,和2个链表合并

    VC6.0下 用C语言实现单向链表的创建、插入,删除节点,和2个链表合并等操作

    数据结构与算法(四):Python实现单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串

    根据链表数据结构的知识,进行初步练习,从单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串四个题目着手,分别进行代码实现。 首先定义单链表类: # 结点类 class Node(object): def _...

    快慢指针法判断单链表有环

    在Java中,判断单链表是否有环的经典方法是使用Floyd的“龟兔...在Main类中,我们创建了一个链表,并故意引入了一个环(最后一个节点指向第二个节点),然后调用hasCycle方法来判断链表是否有环,并打印出相应的结果。

    单向循环链表

    从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item)...

    数据结构第4次作业.docx

    算法提要:深度优先遍历过程中,访问某顶点后,该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边),则有环。 3.编程题: 建立无向图邻接表存储结构,输出深度和宽度优先...

    常考的数据结构题_面试常用

    1.判断链表是否存在环型链表问题:判断一个链表是否存在环,例如下面这个链表就存在一个环: 例如N1->N2->N3->N4->N5->N2就是一个有环的链表,环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1,p2。每次...

    面试考点简版1

    前端面试常考的要点数据结构链表单向链表判断环以及环入口双向链表循环链表各种树b+树b-树b*树红黑树二叉树满二叉树平衡二叉树哈夫曼树完全二叉树二叉查找树队列哈希

    【swjtu】数据结构第4次作业.docx

    算法提要:深度优先遍历过程中,访问某顶点后,该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边),则有环。 3. 上机题 1. 编程题: 建立无向图邻接表存储结构,输出深度和...

    西南交通大学-zhy-数据结构第4次作业.docx

    算法提要:深度优先遍历过程中,访问某顶点后,该顶点的邻接点中有已访问的顶点且该已访问邻接点不是该顶点的上一级递归出发顶点(即存在回边),则有环。 3. 编程题: 建立无向图邻接表存储结构,输出深度和宽度优先...

    interview:PHP高级工程师面试题汇总(2018.05)

    2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public ...

    百度地图毕业设计源码-interview:PHP高级工程面试题汇总(2019.03)

    2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public LNode ...

    leetcode跳跃-Coding_Interview_Guide:《程序员代码面试指南(第二版)》解题笔记

    CD108:反转部分单向链表 CD109:环形单链表的约瑟夫问题(进阶,CD110) CD111:判断一个链表是否为回文结构(时间复杂度O(N),空间复杂度O(N)) CD112:判断一个链表是否为回文结构(进阶,时间复杂度O(N),空间...

    leetcode530-leetcode:leetcode

    判断单向列表是否有环 206 翻转单向链表 237 删除链表元素 203 删除链表多个元素 206 翻转链表 141 环形链表 2021-05-15: 876 获取链表中间节点 20 判断括号是否成对 2021-05-16: 150后缀表达式 224基本计算器 856...

    百度地图毕业设计源码-php-shiti:php-shiti

    2、写一段代码判断单向链表中有没有形成环,如果形成环,请找出环的入口处,即P点 /* *单链表的结点类 */ class LNode{ //为了简化访问单链表,结点中的数据项的访问权限都设为public public int data; public LNode ...

    软件工程之专题九:数据结构知识

    循环链表和单向链表基本一致,差别仅在于算法中循环的条件不是结点的指针是否为空,而是他们的指针是否等于头指针, 循环链表最后一个结点的 link 指针不为 0 (NULL),而是指向了表的前端。 为简化操作,在循环链表...

Global site tag (gtag.js) - Google Analytics