【每日力扣】141. 环形链表与142. 环形链表 II

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害，才敢开始，你需要开始，才会变的非常厉害

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

解题思路

为了判断链表中是否存在环，可以使用快慢指针的方法。快指针每次向前移动两步，慢指针每次向前移动一步，如果链表中存在环，快指针最终会追上慢指针，如果不存在环，快指针会到达链表尾部。

具体步骤如下：

1. 初始化快慢指针，快指针每次移动两步，慢指针每次移动一步。
2. 迭代遍历链表，如果快指针追上了慢指针，则链表存在环；如果快指针到达了链表尾部，则链表不存在环。

代码实现

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;}
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

解题思路

要寻找环形链表的入口节点，可以使用快慢指针的方法。当快慢指针相遇时，让其中一个指针重新指向头节点，并让两个指针以相同速度向前移动，再次相遇的节点就是环的入口节点。这个方法可以证明在相遇点后，再次相遇的节点就是环的入口。

具体步骤如下：

1. 使用快慢指针找到两指针相遇的节点。
2. 将其中一个指针重新指向头节点，保持另一个指针在相遇点。
3. 两个指针以相同速度向前移动，再次相遇的节点即为环的入口节点。

代码实现

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}}return null;}
}