`
美丽的小岛
  • 浏览: 310917 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

单向链表是否有环问题(C)

阅读更多

     问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个环,在顺序遍历链表的时候,程序就会陷入死循环。如何检测一个链表中是否有环,如果检测到环,如何确定环的入口点(即求出环长,环前面的链长)。
      一种比较耗空间的做法是,从头开始遍历链表,把每次访问到的结点(或其地址)存入一个集合(hashset)或字典(dictionary),如果发现某个结点已经被访问过了,就表示这个链表存在环,并且这个结点就是环的入口点。这需要O(N)空间和O(N)时间,其中N是链表中结点的数目。
     如果要求只是用O(1)空间、O(N)时间,应该怎么处理呢?

 

int   is_link_list_cicled(Node*   head)
{
        Node   *p   =   head,   *q   =   head-> next;
        while(p   &&   q)
        {
                if(p   ==   q)
                        return   1;
                p   =   p-> next;
                q   =   q-> next;
                if(!q)
                        return   0;
                q   =   q-> next;
        }
        return   0;
}

 

证明:

 

证明步长法的正确性(追击问题,如果有环则肯定可以相遇):

如果链表有环,不妨假设其环长度为M(>=2)。
p指针首次到达交点(N0)时,q指针已经进入环。
设p=0;q=q-p;
再进过i(i>=0)步后,p=(p+i)%m;q=(q+2*i)%m;
则必存在一个i使得(p+i)%m = (q+2*i)%m。(p,q 都为常数)。

 

问题描述参考:

GoCalf 的Blog

分享到:
评论

相关推荐

    单向链表结点的逐个删除-C语言教程

    本文将详细介绍如何使用C语言实现单向链表结点的逐个删除。 首先,我们要了解单向链表的基本概念。单向链表是由一系列节点组成的线性结构,每个节点包含两部分:数据域和指针域。数据域存储着节点的数据信息,而...

    约瑟夫环单循环链表C语言实现

    题目要求使用C语言编程实现约瑟夫环问题,并通过单向循环链表来管理参与游戏的人。以下是具体的知识点解析: #### 知识点解析 ##### 1. 单向循环链表 单向循环链表是一种特殊的线性表存储结构,其中每个节点包含...

    C/C++经典约瑟夫环问题——带头结点的单向循环链表

    与普通的单向链表不同,它在第一个元素(头结点)之前额外添加了一个结点,通常这个结点不存储实际数据,而是用作链表的标记。这样做的好处是可以简化对链表的处理,比如在插入和删除操作时,不必区分头结点和普通...

    用单向循环链表模拟约瑟夫环

    用C语言编写的约瑟夫环问题解决程序,利用单向循环链表存储结构模拟此过程

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

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

    单向链表,双向链表示例

    单向链表和双向链表各有优劣,根据具体需求选择合适的类型。通过理解和掌握链表的原理及C语言实现,可以提高解决问题的能力,为后续学习更高级的数据结构和算法打下坚实基础。提供的压缩包文件提供了实践链表操作的...

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

    本篇将详细介绍C语言中单向链表的12个基本操作,这些操作对于理解和应用链表至关重要。 1. **创建链表**: 创建链表首先需要定义一个节点结构体,通常包含数据域和指向下一个节点的指针。然后,我们需要一个头指针来...

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

    在这个C语言实现的案例中,我们有24个不同的函数,用于执行单向链表的各种基础操作。下面将详细介绍这些操作以及它们在实际编程中的作用。 1. **创建链表**:初始化链表通常涉及到创建一个空头节点,它不存储任何...

    单向循环链表-仿学生管理系统[详尽注释]

    与普通单向链表不同,循环链表的最后一个节点指向第一个节点,形成一个闭合的环,使得遍历更加方便。接下来我们将深入探讨这个主题。 首先,我们要理解链表的基本概念。链表不同于数组,它的元素(节点)在内存中...

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

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

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

    针对题目要求,我们可以用Python、Java和C语言实现快慢指针算法来检测链表中是否存在环。 ##### 1. Python 实现 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next =...

    c语言 链表 双向链表 双向循环链表

    双向链表与单向链表相比,具有更灵活的操作特性,而双向循环链表则在此基础上增加了循环的特性,使得遍历和操作更加方便。 首先,让我们理解双向链表的基本概念。双向链表中的每个节点包含三个部分:数据域、前向...

    单双向循环链表的转换(C语言)

    // 由于是单向链表,这里将前驱指针设为0 scanf("%d", &x); } return h; } ``` - **功能**:构建单向循环链表。 - **参数**:`lklist h` - 链表头指针。 - **返回值**:`lklist` - 修改后的链表头指针。 #### ...

    数据结构-链表的实现代码(C语言版).rar

    数据结构 -- C语言版 -- 链表的部分实现代码(单向链表、双向链表、循环链表、约瑟夫环等),详细介绍参考数据结构--链表的系列博文。链接为:https://blog.csdn.net/songshuai0223/category_9742561.html。

    用C语言编写的约瑟夫环程序

    该程序以C语言实现的约瑟夫环问题,通过单循环链表结构有效地模拟了这一过程。用户可以输入人数n和初始报数上限m,以及每个人对应的密码,程序将按约瑟夫环规则输出出列顺序。程序设计清晰,逻辑严谨,是理解链表...

    用C语言实现约瑟夫环问题

    在约瑟夫环问题中,我们选择单向循环链表,因为它的头尾可以自然地形成一个闭合的环,非常适合模拟人们围成的圈子。 在C语言中,我们先定义一个链表节点结构体,包含数据(代表人)和指向下一个节点的指针: ```c ...

    c 数据结构 链表源码

    链表有多种类型,包括单向链表、双向链表和循环链表。单向链表的每个节点只能向前指向下一个节点,而双向链表的节点则同时拥有前向和后向指针。循环链表则在链表的最后一个节点指向头节点,形成一个闭合的环状结构。...

    约瑟夫环C语言实现代码

    第二段代码则采用了单向链表的方式来实现约瑟夫环问题。链表节点包含两个字段:编号(num)和密码(code),以及指向下一个节点的指针(next)。 1. **创建链表**: - 首先创建一个头节点,用于标识链表的起始位置...

    C语言-链表HUFFMANTREE.zip

    链表有多种类型,如单向链表、双向链表和循环链表。在C语言中,链表的创建、插入、删除和遍历都需要手动管理内存,这涉及到动态内存分配(如使用`malloc`和`free`函数)以及指针操作。 在单向链表中,每个节点只有...

    推荐多个关于C语言链表资源以及教程

    单向链表只能按一个方向遍历,双向链表则可以在两个方向上移动,循环链表的最后一个节点指向头节点,形成一个环状结构。 在C语言中实现链表,需要理解指针的概念,熟练运用动态内存分配函数如`malloc()`和`free()`...

Global site tag (gtag.js) - Google Analytics