2
LeetCode 第 141 号问题：环形链表
source link: https://www.cxyxiaowu.com/6898.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 141 号问题：环形链表-程序员小吴
当前位置：程序员小吴 > LeetCodeAnimation > LeetCode 第 141 号问题：环形链表
本文首发于公众号「五分钟学算法」，是图解 LeetCode 系列文章之一。
今天分享的题目来源于 LeetCode 上第 141 号问题：环形链表。题目难度为 Easy，目前通过率为 40.4% 。
使用快慢指针的方式去求解 so easy ！
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 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)（即，常量）内存解决此问题吗？
这道题是快慢指针的经典应用。
设置两个指针，一个每次走一步的慢指针和一个每次走两步的快指针。
- 如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环
- 如果含有环，快指针会超慢指针一圈，和慢指针相遇，说明链表含有环。
//author:程序员小吴
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK