内容简介:定义快慢两个指针,慢指针每次前进一步,快指针每次前进两步,若链表有环,则快慢指针一定会相遇。用 unordered_map 充当散列表的功能,每次将链表的节点指针作为键值存入 map,如果检测到当前节点指针已经存在于 map 中则说明链表有环。获取更多精彩,请关注「seniusen」!
2. 解答
2.1 方法 1
定义快慢两个指针,慢指针每次前进一步,快指针每次前进两步,若链表有环,则快慢指针一定会相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
复制代码
2.2 方法 2
用 unordered_map 充当散列表的功能,每次将链表的节点指针作为键值存入 map,如果检测到当前节点指针已经存在于 map 中则说明链表有环。
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_map<ListNode *, char> nodemap; // 散列表功能
ListNode *temp = head;
while (temp)
{
if (nodemap.count(temp) == 1) return true; // 当前节点已存在于 map 中,则说明有环
nodemap[temp] = '0';
temp = temp->next;
}
return false;
}
};
复制代码
获取更多精彩,请关注「seniusen」!
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 141. 环形链表
- Canvas环形倒计时组件
- 利用canvas实现环形进度条
- 使用Golang实现双向环形链表
- 一起撸个环形 Android 图表
- Principle教程:如何完成数字变化+环形加载?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Android开发艺术探索
任玉刚 / 电子工业出版社 / 2015-9-1 / CNY 79.00
《Android开发艺术探索》是一本Android进阶类书籍,采用理论、源码和实践相结合的方式来阐述高水准的Android应用开发要点。《Android开发艺术探索》从三个方面来组织内容。第一,介绍Android开发者不容易掌握的一些知识点;第二,结合Android源代码和应用层开发过程,融会贯通,介绍一些比较深入的知识点;第三,介绍一些核心技术和Android的性能优化思想。 《Andro......一起来看看 《Android开发艺术探索》 这本书的介绍吧!