`

★经典问题—链表中的环问题

 
阅读更多

转载:http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html

作者:胡满超 from:C++博客

 

 

有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。

问题:

1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?

 

一、判断链表是否存在环,办法为:

设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定 相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

 

 

二、找到环的入口点

当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则 fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:

2s = s + nr
s= nr

设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每 次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
        return NULL;

    slow = head;
    while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    }

    return slow;
}
 

扩展问题:

判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

比较好的方法有两个:

一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同 样的结尾点,则两个链表相交。

这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次 一步,相遇的第一点即为两个链表相交的第一个点。

 

分享到:
评论
1 楼 漂泊一剑客 2014-11-11  
如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定 相遇

我来说下我的理解, 当慢的指针走到一圈的时候, 快指针一定是恰好走了两圈,所以他们一定会相遇

相关推荐

    用循环链表实现约瑟夫环问题

    使用c语言中的循环链表及结构体实现约瑟夫环问题

    C语言经典但链表,C语言经典但链表,C语言经典但链表

    链表是一种基础且重要的数据结构,它在计算机科学和编程,尤其是C语言中扮演着核心...通过熟练运用链表,可以解决许多实际问题,如数据存储、搜索、排序等。因此,深入学习和实践链表对于提升编程技能具有重要意义。

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

    在经典的约瑟夫环问题中,参与者按照顺时针方向按编号排列,每经过一定数量的参与者(称为步长),编号为当前步长的参与者就会“出列”。这个过程一直持续到链表为空,即所有参与者都已出列。 在C/C++中,我们通常...

    C++语言约瑟夫环,双向链表

    在编程领域,约瑟夫环(Josephus Problem)是一个经典的理论问题,它涉及到数组或链表数据结构的操作。这个问题的基本设定是:人们围成一个圈,按照一定的规则从某个人开始报数,每次数到特定数值的人会被排除,然后...

    用链表表示循环链表的约瑟夫环的问题的源代码

    约瑟夫环问题是一个经典的计算机科学问题,源于古罗马数学家约瑟夫提出的一个设想。问题描述如下:假设有一群人围成一个圈,从某个人开始按顺时针方向依次报数,每数到特定数值的人会被剔出圈子,然后从下一个人继续...

    约瑟夫环_双向链表(c++做的)

    在约瑟夫环问题中,双向链表可以更好地模拟人们在圆圈中的顺序关系。 下面我们将深入探讨如何使用C++实现约瑟夫环问题的双向链表解决方案: 1. **链表节点定义**:首先,我们需要定义一个链表节点结构体,包括一个...

    约瑟夫环 C++ 链表

    在C++编程中,我们可以利用链表数据结构来解决这个问题。 链表是一种线性数据结构,它不依赖于内存的连续性,每个元素称为节点,包含数据和指向下一个节点的指针。对于约瑟夫环问题,我们可以创建一个单链表,每个...

    c++链表,解决约瑟夫环问题

    在这个特定的场景中,我们利用链表来解决著名的约瑟夫环(Josephus Problem)问题。约瑟夫环问题是一个理论上的问题,其背景是古代犹太人约瑟夫在战争中为了避免被敌人俘虏,让幸存者围成一个圈,按照一定的规则每隔...

    循环链表实现约瑟夫环问题

    循环链表实现约瑟夫环问题 约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又...

    约瑟夫环问题(链表和数组)

    总的来说,约瑟夫环问题的解决方法展示了数组和链表两种数据结构的应用,同时也体现了动态规划和循环结构在解决问题中的重要性。通过理解和实践这两种实现,不仅可以提升编程技能,还能深入理解数据结构和算法在解决...

    用链表表示循环链表的约瑟夫环的问题的源代码的报告

    约瑟夫环问题是一个经典的计算机科学问题,通常用链表来解决。本文将深入探讨如何使用链表来实现循环链表的约瑟夫环问题,并提供相关的源代码。 一、问题概述 假设有一群人围成一个圈,从某个人开始报数,数到特定...

    java编写的循环链表来实现约瑟夫环

    循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释

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

    在约瑟夫环问题中,单向循环链表非常适合模拟游戏参与者围成一圈的情形。 **特点:** - **循环特性:** 最后一个节点指向第一个节点。 - **单向链接:** 每个节点只保存指向其后继节点的指针。 - **动态扩展:** ...

    数组表示循环链表约瑟夫环

    总的来说,使用数组表示循环链表来解决约瑟夫环问题是一种巧妙的方法,它结合了数组的高效访问和链表的循环特性,为编程挑战提供了一个有趣的解决方案。通过理解这个算法,不仅可以提升编程技巧,还能深入理解数据...

    约瑟夫环的链表实现——数据结构

    在这个问题中,我们可以使用循环链表,因为约瑟夫环的最后一个元素会连接到第一个元素形成一个封闭的环。 约瑟夫环问题的链表实现通常分为以下步骤: 1. **初始化链表**:首先创建一个循环链表,链表的节点代表...

    约瑟夫环 动态链表 处理

    在本程序中,约瑟夫环问题通过动态链表来实现。动态链表是一种灵活的数据结构,它可以在运行时动态地分配内存,从而使得链表的长度可以根据需要变化。动态链表的每个节点包含两个部分:数据部分(存储实际的数据)和...

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

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

    c++循环链表解决约瑟夫环问题

    约瑟夫环问题源于古罗马历史的一个故事,后来成为计算机科学中的一个经典问题。问题的大致描述是这样的:有n个人围成一个圈,每个人都有一个对应的密码(正整数),并且给定了一个初始报数上限值m。从第一个人开始,...

    约瑟夫环(链表实现)

    约瑟夫环是一种经典的算法问题,它的主要思想是使用链表来模拟一个环形结构,然后通过遍历这个环形结构来实现约瑟夫环的操作。下面我们将详细介绍约瑟夫环的链表实现。 首先,我们需要定义链表结点结构体`node`,它...

Global site tag (gtag.js) - Google Analytics