Leetcode 分类刷题 —— 链表类（Linked List）
1、题目
Leetcode 141. Linked List Cycle (Linked List Cycle II)
给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
2、思路
方法一：用哈希表（HashSet）存储所有已经访问过的节点，每次我们到达一个节点：
如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。
方法二：快慢指针若相遇则判断有环：适用于链表中获取倒数第k个元素、获取中间位置的元素、
判断链表是否存在环、判断环的长度等和长度与位置有关的问题。
3、快慢指针 Java 代码
public class Solution {
public boolean hasCycle(ListNode head) {
// 空链表、单节点链表一定不会有环
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
参考文章：
https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
