原题
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 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/
相关推荐
-
leetcode151-翻转字符串里的单词
原题 给定一个字符串，逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he...
-
leetcode26-删除排序数组中的重复项
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空...
-
leetcode210-课程表II
原题 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0...
-
leetcode450-删除二叉搜索树中的节点
原题 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。 一...
-
leetcode21-合并两个有序链表
原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入： 1->2->4, 1->3->4 输出： 1->1->2->3-...
-
剑指offer50-第一个只出现一次的字符
原题（来源Leetcode） 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s...
-
leetcode54-螺旋矩阵
原题 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6...
-
leetcode387-字符串中的第一个唯一字符
原题 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"...
-
leetcode328-奇偶链表
原题 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空...
-
leetcode104-二叉树的最大深度
原题 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例：给定二叉树 [3,9,20,null...