`
zhu_jinlong
  • 浏览: 5258 次
  • 性别: 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); 
  }
分享到:
评论

相关推荐

    算法:给定一个链表,判断链表中是否存在环

    快慢指针算法是一种用于检测链表中是否存在环的有效方法,也称为“龟兔赛跑”算法。这种方法使用两个指针,一个快指针(每次移动两步),一个慢指针(每次移动一步)。 - **初始化**:将快慢指针都指向链表头结点。...

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

    本篇文章将深入探讨如何判断单向链表是否包含环,并在存在环的情况下计算环的入口节点。 判断链表中是否存在环的典型方法是使用快慢指针。快慢指针的初始位置都是链表的头节点。快指针每次移动两个节点,而慢指针...

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

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

    单向链表的功能

    单向链表的功能远不止这些,还包括合并两个已排序的链表、判断链表是否有环、获取链表中间节点等。理解和熟练掌握单向链表的操作对于编程学习至关重要,特别是在处理动态数据结构和优化算法效率时。通过实践和练习,...

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

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

    数据结构:单向循环链表源码

    3. **插入和删除操作**:插入和删除节点的操作与普通单向链表类似,但需要考虑链表是否为空及插入位置的判断。 **单向循环链表常见操作** 1. **创建链表**:初始化链表,通常创建一个节点作为链表的首节点。 2. **...

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

    总结,本篇文章介绍了C语言实现单向链表的基本操作,包括创建链表、插入节点、删除节点、判断链表是否有环以及合并两个已排序的链表。通过理解这些基本操作,可以为更复杂的数据结构和算法打下坚实的基础。在VC6.0...

    两列单向链表相同值查询设计

    这些函数中有一些问题需要指出: - 在插入节点前,需要创建新的节点对象,而不是直接操作指针`insert`。 - 使用`goto`语句来处理错误情况并不是一个好的编程习惯,可以考虑使用函数返回值或者异常处理机制来替代。 -...

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

    本篇文章将详细探讨如何判断两个单向链表是否相交的问题,以及相应的解决方案。 #### 问题背景 在实际应用中,尤其是在大型系统开发过程中,可能会遇到两个链表相交的情况。例如,当两个链表共享部分节点时,如果不...

    实用单向链表的基本操作函数24个C语言版

    13. **判断链表是否有环**:使用快慢指针(Floyd's Cycle-Finding Algorithm)来检测链表中是否存在环。 14. **找到环的起始节点**:如果链表有环,可以进一步找到环的起始节点。 15. **节点交换**:交换链表中两...

    多瑟夫环问题单向循环链表

    + EmptyList(L):判断链表L是否为空表。 + ListLength(L):返回链表L中的数据元素个数。 + GetElem(L, pos, &e):返回链表L中的第pos个数据元素的值。 + LocateElem(L, e):返回链表L中第一个与e相同的元素的...

    C语言单向链表的基本操作12个

    9. **判断链表循环**: 使用Floyd判圈法(快慢指针)检查链表是否有环。快指针每次移动两步,慢指针每次移动一步,如果两者相遇,链表有环;若快指针到达NULL,链表无环。 10. **链表排序**: 可以使用插入排序、归并...

    循环链表,对应严书的循环链表一章 本文件仅包含单向的循环链表

    6. **判断链表是否有环**:检查链表是否为循环链表,这在处理复杂链表结构时非常有用。 在C++中,我们还可以利用STL(Standard Template Library)中的`list`容器,它提供了一种高效且易于使用的双向循环链表实现。...

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

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

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

    题目要求编写一个程序,用于判断两个单向链表是否相交。这里假设两个链表均不包含环。为了简化问题,我们将重点放在如何有效地确定两个链表是否相交上,并探索不同的解决方案。 #### 解法一:直观的想法 最直观的...

    单向循环链表操作实现.zip

    8. **判断链表是否为空**:检查头节点的next指针是否指向自身,如果指向自身则为空链表。 在实际编程中,单向循环链表常用于解决各种问题,如队列实现、图形遍历、数据缓存等。它提供了比线性链表更高效的某些操作...

    2019年高级php工程师面试题及答案.pdf

    2. 链表数据结构的应用:文档中提到写代码判断单向链表中是否有环,并找出环的入口,这是数据结构中链表的经典问题。在PHP中可以通过快慢指针的方法来判断链表中是否存在环,并通过调整指针位置找到环的起点。这一...

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

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

    leetcode-链表笔记

    Linked List Cycle**:判断链表是否有环,如有,找到环的入口节点。 - **19. Remove Nth From End**:移除链表中的第 n 个节点。 - **206. Reverse Linked List**:反转整个链表。 - **21. Merge Two Sorted ...

Global site tag (gtag.js) - Google Analytics