重庆速代网络科技_深圳app开发哪家专业_新网站如何快速收录_有什么平台可以发广告

解题思路：

1. 初始化两个指针： slow 和 fast，均指向链表头节点 head。
2. 遍历链表： slow 每次移动一步，fast 每次移动两步。
3. 判断条件： 如果 fast 或 fast.next 为 null，说明链表无环，返回 false；如果 slow 和 fast 相遇，说明链表有环，返回 true。

Java代码：

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

复杂度分析：

• 时间复杂度： O(n)，其中 n 是链表长度。最坏情况下，快指针遍历完整个链表。
• 空间复杂度： O(1)，仅使用两个额外指针。

解题思路：

1. 判断是否有环： 使用快慢指针（快指针每次移动两步，慢指针每次移动一步）遍历链表。如果快指针追上慢指针，则说明存在环。
2. 确定环的入口： 将慢指针重置到链表头，快指针保持在相遇点。此时，两个指针以相同速度移动，再次相遇的节点即为环的入口。

Java代码：

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

复杂度分析：

• 时间复杂度： O(n)，其中 n 是链表长度。快指针最多遍历链表两次（第一次找相遇点，第二次找入口）。
• 空间复杂度： O(1)，仅使用两个额外指针（slow 和 fast）。