每日一道 LeetCode (34):环形链表
2023-09-14 09:00:02 时间
每天 3 分钟,走上算法的逆袭之路。
前文合集
代码仓库
GitHub: https://github.com/meteor1993/LeetCode
Gitee: https://gitee.com/inwsy/LeetCode
题目:环形链表
题目来源:https://leetcode-cn.com/problems/linked-list-cycle/submissions/
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 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
解释:链表中没有环。
解题方案
这道题其实蛮简单的,就是要看整个链表上有没有成环。
我开辟一个空间,比如一个哈希表或者其他什么的,把链表上的每一个元素一个一个往里面放,然后看看是否存在,如果存在就说明成环了,如果不存在,说明没有成环。
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (set.contains(head)) {
return true;
} else {
set.add(head);
}
head = head.next;
}
return false;
}
这种方案开辟一个新的空间,那么能不能不开辟新的空间呢?
public boolean hasCycle_1(ListNode head) {
while (head != null) {
if (head == head.next) {
return true;
}
if (head.next != null) {
head.next = head.next.next;
}
head = head.next;
}
return false;
}
这个方案是如果下一个元素不为空,则把 head.next
指向 head.next.next
,相当于是在整个链表上去掉了 head.next
,直到最后,如果成环的话,那么 head == head.next
。
相关文章
- Java实现 LeetCode 795 区间子数组个数 (暴力分析)
- Java实现 LeetCode 594 最长和谐子序列(滑动窗口)
- Java实现 LeetCode 488 祖玛游戏
- Java实现 LeetCode 477 汉明距离总和
- Java实现 LeetCode 382 链表随机节点
- Java实现 LeetCode 138 复制带随机指针的链表
- Java实现 LeetCode 25 K个一组翻转链表
- Java实现 LeetCode 25 K个一组翻转链表
- Java实现 LeetCode 23 合并K个排序链表
- Java实现 LeetCode 21 合并两个有序链表
- Java实现 LeetCode 131 分割回文串
- 每日一道 LeetCode (18):删除排序链表中的重复元素
- LeetCode(20):有效的括号
- (链表专题) 725. 分隔链表 ——【Leetcode每日一题】
- (链表专题) 328. 奇偶链表 ——【Leetcode每日一题】
- (链表专题) 234. 回文链表——【Leetcode每日一题】
- (链表专题) 445. 两数相加 II ——【Leetcode每日一题】
- [LeetCode] 148. 排序链表 ☆☆☆(归并排序)
- 【Leetcode刷题Python】92.反转链表II
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- LeetCode 23. 合并K个升序链表
- LeetCode 141. 环形链表
- 【LeetCode】39. 组合总和
- 【LeetCode】翻转链表II