从有环链表中如何获得环的长度

节点类

@Data
public class Node {
/**
* 用于保存节点中的数据
*/
private Object data;
/**
* 用于保存下一个节点的地址值
*/
private Node next;

public Node(Object data) {
this.data = data;
}

public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}

实现类

package day04;

/**
* @Author yqq
* @Date 2022/05/09 09:46
* @Version 1.0
* 从有环链表中，获得环的长度
*/
public class Test06 {
public static void main(String[] args) {
//创建一个单链表
Node lastNode = new Node(55);
Node node4 = new Node(44,lastNode);
Node node3 = new Node(33,node4);
Node node2 = new Node(22,node3);
Node headNode = new Node(11,node2);
lastNode.setNext(node2);
int len = getLen(headNode);
System.out.println(len);
}

/**
* 获得快慢指针相交的节点
* @param headNode
* @return
*/
public static Node meetNode(Node headNode){
//处理headNode为null的情况
if (headNode == null)
return null;
//定义一个快指针，指向headNode，每次向后移动两次
Node fast = headNode;
//定义一个慢指针，指向headNode，每次往后移动一次
Node slow = headNode;
//定义一个循环用于单链表是否有环
while (fast != null && fast.getNext() != null){
//设置快指针和慢指针每次向后移动
fast = fast.getNext().getNext();
slow = slow.getNext();
//如果fast和slow指向同一个节点，则表示单链表有环
if (fast == slow)
return fast;
}
return null;
}

/**
* 获得有环链表环的长度
* @param headNode
* @return
*/
public static int getLen(Node headNode){
//获得快慢指针相交的节点
Node meetNode = meetNode(headNode);
//处理meetNode为null的情况
if (meetNode == null)
return 0;
//定义一个变量保存环中节点的个数
int size = 0;
//从meetNode节点开始，遍历环中节点
//定义一个临时节点，用于辅助遍历单链表
Node tempNode = meetNode;
//定义死一个循环，用于遍历环中的节点
while (true){
//让tempNode指向它的下一个节点
tempNode = tempNode.getNext();
//更新size的值
size++;
//如果tempNode和meetNode指向同一个节点，就停止遍历操作
if (tempNode == meetNode)
break;
}
//返回环中节点的个数
return size;
}
}