原题
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例1:
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环，其尾部连接到第二个节点。
示例2:
输入: head = [1,2], pos = 0
输出: true
解释: 链表中有一个环，其尾部连接到第一个节点。
示例3:
输入: head = [1], pos = -1
输出: false
解释: 链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
解法
思想
- HashSet
依次将获取到的链表元素插入一个HashSet中，看是否有相同元素。 - 双指针
一个快指针一个慢指针，如果有环快指针总会赶上慢指针。
代码
HashSet：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
Set<ListNode> set = new HashSet<>();
ListNode cur = head;
while(cur.next!=null){
if(set.contains(cur)) return true;
set.add(cur);
cur = cur.next;
}
return false;
}
}
双指针：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
ListNode slow = head;
ListNode fast = head;
while (slow!=null && fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode141-%e7%8e%af%e5%bd%a2%e9%93%be%e8%a1%a8/
相关推荐
-
leetcode19-删除链表的倒数第N个节点
原题 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为...
-
leetcode152-乘积最大子数组
原题 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出:...
-
剑指offer40-最小的k个数
原题（来源Leetcode） 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： ...
-
蓝桥杯试题-小数第n位
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。 如果我们把有限小数的末尾加上无限多个...
-
leetcode77-组合
原题 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [...
-
程序员面试金典17.16-按摩师
原题（来源Leetcode） 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，...
-
二叉树中序遍历-折纸问题
原题（来源牛客网） 请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯...
-
程序员面试金典01.06-字符串压缩
原题（来源Leetcode） 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字...
-
leetcode1160-拼写单词
原题 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字...
-
leetcode205-同构字符串
原题 给定两个字符串 s 和 t，判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换，同时保留字符的顺...