计算环形链表,环的长度
该代码用于检测链表中是否存在环,并返回环的长度。
- 首先判断链表头结点是否为空,如果为空则直接返回0。
- 定义两个指针,fast和slow,初始值都指向头结点。
- 使用快慢指针的方式进行遍历链表,快指针每次移动两步,慢指针每次移动一步,直到快指针为空或者快指针的下一个节点为空为止。
- 在遍历过程中如果快指针和慢指针相遇,则说明链表存在环。
- 将快指针重新指向头结点,然后快指针和慢指针以相同的速度继续遍历链表,直到两个指针再次相遇。
- 此时快指针和慢指针的相遇点即为环的起始位置。
- 将快指针指向相遇点的下一个节点,然后使用一个变量step记录步数,每移动一步step加1,直到快指针再次回到相遇点为止。
- 返回步数step即为环的长度。
// 检测单链表中是否存在环,并返回环的长度
public int detectCycle(ListNode head) {// 如果头节点为null,直接返回0,表示链表中无环if (head == null) {return 0;}// 初始化快慢指针,都指向头节点ListNode fast = head;ListNode slow = head;// 使用快慢指针检测环while (fast != null && fast.next != null) {fast = fast.next.next; // 快指针每次移动两步slow = slow.next; // 慢指针每次移动一步// 如果快慢指针相遇,表示链表中存在环if (fast == slow) {// 将快指针重新指向头节点,寻找环的起始位置fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}// 找到环的起始节点后,计算环的长度ListNode cycleStart = slow;fast = slow.next;int step = 1;while (fast != cycleStart) {fast = fast.next;step++;}// 返回环的长度return step;}}// 如果未检测到环,返回0return 0;
}