环路检测
难度:
标签:
题目描述
Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0
Example 3:
Input: head = [1], pos = -1 Output: no cycle
Follow Up:
Can you solve it without using additional space?
代码结果
运行时间: 60 ms, 内存: 17.9 MB
/*
* Java Stream API 不能直接处理链表问题，尤其是涉及到环检测。
* 但是可以通过构建辅助方法来实现相似的功能。
* 以下是使用 Java 代码来模拟 Stream 风格的链表环检测方法。
*/
public class Solution {
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
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) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}解释
方法:
这个题解使用了快慢指针的方法来检测链表中是否存在环，并找到环的入口。首先，设置两个指针s（慢指针）和f（快指针），它们都从头节点开始。慢指针每次移动一步，快指针每次移动两步。如果链表中存在环，那么快慢指针最终会在环内相遇。在快慢指针相遇后，将快指针重新指向头节点，然后快慢指针都每次移动一步，直到它们再次相遇的位置，这个位置就是环的入口。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在快慢指针相遇后，将快指针重新指向头节点并以相同速度移动，它们再次相遇的位置就是环的入口？
▷🦆
如果链表的长度非常大，快指针移动两步是否可能导致跳过环的入口？
▷🦆
在快慢指针的方法中，如何保证当快慢指针再次相遇时，它们的位置一定是环的入口，而不是环中的其他位置？
▷🦆
如果链表中的环非常小，例如只包含两个节点，这个算法的逻辑是否还适用？
▷