• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

单链表有环问题

技术杂谈 勤劳的小蚂蚁 3个月前 (01-13) 88次浏览 已收录 0个评论 扫描二维码


小咖是某某计算机专业的学生。linglingling,伴随这铃声,同学们都准时来上课了。
老师:这节课是计算机课,我们学习了单链表,请同学说一下什么是单链表
同学们纷纷举起了手。好,小白你来说。

小白:单链表是一种线性表,它的存储单元可以不是连续的,从头节点开始,每个节点都有一个指针,指向下一个节点,最后一个节点指向null,头节点不被指向。
老师:好,那么谁来说一下链表的这种结构有什么优点呢?
同学们纷纷举起了手。好,小黄你来说。
小黄:线性表的一种链式表的在存储空间中可以是不连续的,因此存储密度较低,还有增删的时候只需要改变指针的指向就可以了,而不是像顺序表那样,比如你要在某个位置添加一个元素,那么其他的元素都要向后移,因此链式表增删相对较快些。
老师:好,大家掌握的不错啊,那么大家思考一个问题,怎么判断一个单链表是否有环。

如图,这样的单链表就是有环的链表。

注:数字1-10代表节点1-10,节点存储值和指针。

老师:好,小红同学你来说。
小红:两层循环,第一层循环从头遍历,第二层循环从头遍历到第一层循环当前的节点,如果存在相同的节点,那么链表有环。
老师:好,这样做确实是可以判断是否有环,但是效率并不高,遍历两次时间复杂度o(n^2),由于没有开辟额外的空间,所以空间复杂度o(1)。哪位同学还有更好的方法吗。
老师:好,小明你来说一下。
小明:一层循环,创建一个hashset,把节点放到hashset中,如果出现相同的节点,说明单链表有环。
老师:好,小明同学采用了空间换时间的方法,此时的时间复杂度o(n),由于开辟了和链表单独相关的n的空间,所以空间复杂度o(n)。那还有没有更好的方法呢。
老师:谁是计算机课带表啊。
课带表:

老师:那么你来说说,有什么更好的方法。
课代表:
如果两个人在环形的跑道上赛跑,快的人总会再次追上慢的。
因此我们可以假设用两个指针比如两个赛跑的同学,一个快指针,一个慢指针,我们称为快慢指针方法。
那么我们来说一下说它是实现思路:
快指针每次移动两步,慢指针每次移动一步,如果两个节点相等,则说明有环,返回true,否则返回false。
代码实现大概是是这个样子的。
    Node  fast = head;   
    Node  slow = head;   
    while(fast.next != null)  
    {  
        fast = fast.next.next;  
        slow = slow.next;  
        if (slow == fast)   
            return true;  
    }  
    return false;  
老师:非常好,这个方法的时间复杂度为o(n),空间复杂度为o(1)。请大家回去思考一个问题,如何判断单链表是否有交点。下节课老师提问,同学们下课。

    丨极客文库, 版权所有丨如未注明 , 均为原创丨
    本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
    转载请注明原文链接:单链表有环问题
    喜欢 (0)
    [247507792@qq.com]
    分享 (0)
    勤劳的小蚂蚁
    关于作者:
    温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

    您必须 登录 才能发表评论!

    • 精品技术教程
    • 编程资源分享
    • 问答交流社区
    • 极客文库知识库

    客服QQ


    QQ:2248886839


    工作时间:09:00-23:00