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

节点类

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

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