黄页网站推广app软件,郑州房地产网站建设,华为商城,贵阳专业建网站文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
做了一堆单链表单指针的题目#xff0c;这次是个双指针题#xff0c;这里双指针的作用非常明显。 题目
判断给定的链表中是否有环。如果有环则返回true#xff0c;否则返回fal… 文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
做了一堆单链表单指针的题目这次是个双指针题这里双指针的作用非常明显。 题目
判断给定的链表中是否有环。如果有环则返回true否则返回false。
数据范围链表长度 0≤n≤10000链表中任意节点的值满足 ∣val∣100000 要求空间复杂度 O(1)时间复杂度 O(n)
输入分为两部分第一部分为链表第二部分代表是否有环然后将组成的head头结点传入到函数里面。-1代表无环其它的数字代表有环这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时对应的链表结构如下图所示 示例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 *fasthead;ListNode *slowhead;//这里nullptr和NULL效果一样但在某些地方有点不同可以查一下互联网//while (fast!nullptrfast-next!nullptr) {while (fast!NULLfast-next!NULL) {fastfast-next-next;slowslow-next;if(fastslow)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::setListNode* node_set;while(head){//如果查找head节点对应的内存地址找到相同的了并且这个地址不是set的最后一个元素那么就是有环if(node_set.find(head)!node_set.end()){return true;}node_set.insert(head);headhead-next;}return false;}
};总结
如何判断链表有环的情况之前没遇到过。所以第一次做的时候有点懵逼同时对双指针的使用上并不是特别熟悉这道题在初期思考的时候都是想着怎么用单链表加标志位的情况来判断。还是有点草率了。
