从单链表中如何取出环的起始点

节点类

@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/10 14:54
* @Version 1.0
* 环形单链表中取出还的起始点
*/
public class Test07 {
public static void main(String[] args) {
Node lastNode = new Node(77);
Node node6 = new Node(66,lastNode);
Node node5 = new Node(55,node6);
Node node4 = new Node(44,node5);
Node node3 = new Node(33,node4);
Node node2 = new Node(22,node3);
Node headNode = new Node(11,node2);
lastNode.setNext(node3);
//获取环表长度
int length = getLength(headNode);
//获得环起始节点
Node beginNode = getBeginNode(headNode, length);
System.out.println("环的起始点："+ beginNode.getData());
}

/**
* 获取环形链表长度
* @param headNode
* @return
*/
public static int getLength(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;
}
/**
* 获得快慢指针相交的节点
* @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 Node getBeginNode(Node headNode,int size){
if (headNode == null || size == 0)
return null;
//定义两个指针节点，分别初始化为headNode
Node first = headNode;
Node second = headNode;
//让first指针节点往后移动size次
for (int i = 0; i < size; i++) {
first = first.getNext();
}
while (true){
//让first指针每次向后移动一次
first = first.getNext();
//让second指针每次向后移动一次
second = second.getNext();
//当first和second指向同一个节点，则当前节点为单链表环的起点节点
if (first == second)
return first;
}
}
}