C/C++ BM6判断链表中是否有环

这篇具有很好参考价值的文章主要介绍了C/C++ BM6判断链表中是否有环。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

做了一堆单链表单指针的题目,这次是个双指针题,这里双指针的作用非常明显。


题目

判断给定的链表中是否有环。如果有环则返回true,否则返回false。

数据范围:链表长度 0≤n≤10000,链表中任意节点的值满足 ∣val∣<=100000
要求:空间复杂度 O(1),时间复杂度 O(n)

输入分为两部分,第一部分为链表,第二部分代表是否有环,然后将组成的head头结点传入到函数里面。-1代表无环,其它的数字代表有环,这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时,对应的链表结构如下图所示:
C/C++ BM6判断链表中是否有环,# 刷题,c语言,c++,链表
示例1
输入:{3,2,0,-4},1
返回值:true
说明:第一部分{3,2,0,-4}代表一个链表,第二部分的1表示,-4到位置1(注:头结点为位置0),即-4->2存在一个链接,组成传入的head为一个带环的链表,返回true

示例2
输入:{1},-1
返回值:false
说明:第一部分{1}代表一个链表,-1代表无环,组成传入head为一个无环的单链表,返回false

示例3
输入:{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值:true

解决方案一

1.1 思路阐述

采用双指针法。

对于一个链表,链表中的节点的值可能会相同,所以我们很难通过值来判断是否有环。但是在链表中,每一个链表节点在内存中的地址是不一样的,所以我们比较节点与节点之间的地址信息。

双指针法:一个指针fast每次间隔一个节点进行遍历,一个指针slow每次按序遍历。通常,间隔遍历的指针fast会首先到达链表表尾,或者表尾的下一个指针即nullptr。那么如果对于有环的情况,fast会再次回到它所指的前面的节点;slow指针按序遍历,依次前进一个,如果链表没有环,那么slow和fast都会到达链尾。如果有环,fast一定会到达slow所指的节点位置。

这里打个比方,A和B同时在400m跑道上赛跑,A跑得快,B跑的慢。同时起跑,A跑的比B快,AB之间的距离不断拉大,A到后面超过B一圈了,那么超过B一圈的时候,A和B又在跑道上碰上了。这就是我上面写的如果有环,fast一定会到达slow所指的节点位置。

对于循环的终止条件:我们只需要判断fast指针是否遍历到链尾或者链尾的后一个节点空指针。

1.2 源码

#include <cstddef>
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head)
            return false;

        ListNode *fast=head;
        ListNode *slow=head;
		//这里nullptr和NULL效果一样,但在某些地方有点不同,可以查一下互联网
        //while (fast!=nullptr&&fast->next!=nullptr) {
        while (fast!=NULL&&fast->next!=NULL) {

            fast=fast->next->next;
            slow=slow->next;

            if(fast==slow)
                return true;
        }
        return false;
    }
};

解决方案二

2.1 思路阐述

思路一是用双指针,思路二就是哈希了。

在C++中的STL有一个set容器,在C++中,std::set 是标准模板库(STL)中的一个容器,它是一个有序的关联容器,用于存储不重复的元素。每个元素在 std::set 中都有唯一的键值,而且它们按照升序进行排序。

所以刚才我们提到的比较节点是比较内存地址而非值,所以我们在set中存放的应该是ListNode *

接下来的事情就很简单了,我每次存一个内存地址,如果出现内存地址相同的情况,那就是有环。

2.2 源码

class Solution {
public:
    bool hasCycle(ListNode *head) {
        std::set<ListNode*> node_set;
        while(head)
        {
        //如果查找head节点对应的内存地址找到相同的了,并且这个地址不是set的最后一个元素,那么就是有环
            if(node_set.find(head)!=node_set.end())
            {
                return true;
            }
            node_set.insert(head);
            head=head->next;
             
        }
        return false;
         
    }
};

总结

如何判断链表有环的情况,之前没遇到过。所以第一次做的时候有点懵逼,同时对双指针的使用上并不是特别熟悉,这道题在初期思考的时候都是想着怎么用单链表加标志位的情况来判断。还是有点草率了。文章来源地址https://www.toymoban.com/news/detail-805291.html

到了这里,关于C/C++ BM6判断链表中是否有环的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 链表是否有环、环长度、环起点

    问题引入         如何检测一个链表是否有环,如果有,那么如何确定环的长度及起点。 引自博客:上述问题是一个经典问题,经常会在面试中被问到。我之前在杭州一家网络公司的电话面试中就很不巧的问到,当时是第一次遇到那个问题(毕竟太菜,没有专门准备过算

    2024年02月15日
    浏览(35)
  • 哪些方法可以判断出一个有向图是否有环

    使用 深度优先遍历 ,若从有向图上的某个顶点u出发,在 DFS(u)结束之前出现一条从顶点v到u的边,由于v在生成树上是u的子孙,则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。 拓扑排序 时,当某顶点不为任何边的头时才能加入序列,存在环时环中的

    2024年02月12日
    浏览(44)
  • LeetCode刷题---两两交换链表中的节点

    个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏:                   前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的   我讲述题目会把讲解部分分为3个部分: 1、题目解析 2、算法原理思路讲解  3、

    2024年02月05日
    浏览(53)
  • 【LeetCode刷题-链表】--82.删除排序链表中的重复元素II

    由于链表是排好序的,所以只需要对其进行一次遍历即可,比较相邻节点对应的值

    2024年02月06日
    浏览(39)
  • Leetcode刷题之两两交换链表中的结点和相交链表

    只有把抱怨环境的心情,化为上进的力量,才是成功的保证。       ——罗曼·罗兰 目录 🍉一.相交链表 💐1.双指针 🍍2.计算长度加双指针 🍒二.两两交换链表中的结点  🍌1.迭代  给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点

    2024年02月04日
    浏览(33)
  • Leetcode刷题之回文链表和交换链表中的结点

    竭力履行你的义务,你应该就会知道,你到底有多大的价值。      --列夫.托尔斯泰 目录 🪴一.回文链表 🌻1.快慢指针  🍁2.把值存入数组中,然后使用双指针  🌼二.交换链表中的结点  🍂1.快慢指针 给你一个单链表的头节点  head  ,请你判断该链表是否为回文链表。如

    2024年02月04日
    浏览(50)
  • 记录力扣热题-100——从链表中找到刷题感觉

    狮子此前已经很久没有碰过算法题了,对于之前好不容易攒起来的题感又没了…最近准备面试,又得重新将其捡起来。算法题是一种很奇妙的东西,如果刚开始刷很难找得到感觉,总得一步一步慢慢来,心急吃不到热豆腐,狮子建议如果刚开始刷题,先从简单的链表题开始刷

    2024年02月12日
    浏览(38)
  • Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

    思路:链表相关的问题建议就是画图去解决,虽然理解起来很容易,但就是写代码写不出来有时候,依次去遍历第二节点如果与前一个节点相等则跳过,不相等则遍历第三个节点

    2024年02月22日
    浏览(63)
  • 算法刷题Day4 两两交换链表中的节点+删除链表的倒数第N个结点+链表相交+环形链表

    使用dummy节点可以极大地简化过程 有个地方折磨了我有一会儿,是粗心导致的,而且提示的错误也很难发现是哪里导致的。就是在case为 head = [1], n = 1 时,最后释放了 tmp 之后(此时 tmp 刚好指向 head ,我还 return head; ,意思就是操作了已经被我释放的内存, leetcode 就报错了

    2024年02月09日
    浏览(46)
  • leetcode 234.判断链表是否为回文

    给定一个单链表,判断它是否是回文。 输入: 1-2 输出: false 输入: 1-2-2-1 输出: true 判断链表是否为回文,可以通过翻转链表后半部分并比较两半部分是否相同来实现。具体步骤如下: 使用快慢指针找到链表的中间节点。 翻转链表的后半部分。 比较前半部分和翻转后的后半部

    2024年01月19日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包