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

节点类

@Datapublic 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; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。