介绍
判断单链是否循环,并且找出第一个循环节点。
思路
【判断单链是否循环】:如果单链是循环的,那么循环部分就是封闭的。这好比一个田径运动场,当两个人跑步时,开始虽然有一定的间距,但他们迟早会相遇的。
顺其自然的我们从中抽取一个数学模型,一个是步长Steps(对应两人刚开始跑步时的间距);一个是判断单链循环的条件nodeX==nodeY(两人“相遇”)。
【找出第一个循环节点】:我想过好多其它方法,实现起来都比较难,后来出去骑行了两个小时,回来后就想到借助Hash存储,Hash元素包含判断,结果实现起来既容易,又好懂。
比如:下图就是一个循环单链,第一个循环节点为3。
package shuai.study.link.circle; import java.util.HashSet; import java.util.Set; class Node { String data = null; Node nextNode = null; public Node(String data, Node nextNode) { this.data = data; this.nextNode = nextNode; } } ///////////////////////////////////////////////////////////////////////////////////////// class SingleCircleLink { Node firstNode = null; Node nodeX = null; Node nodeY = null; public SingleCircleLink(Node firstNode) { this.firstNode = firstNode; this.nodeX = firstNode; this.nodeY = firstNode; } public boolean isSingleCircleLink() { /* * This while block judge whether this link is circle or not. */ while (nodeY != null && (nodeY = nodeY.nextNode) != null && nodeX != nodeY) { nodeX = nodeX.nextNode; nodeY = nodeY.nextNode; } /* * if Node.next is null, then it illustrates this link isn't circle link. */ return nodeY != null; } public void printFirstCircleNode(boolean isSingleCircleLinkFlag) { if (isSingleCircleLinkFlag) { System.out.println("This is single circle link"); Set<Node> hashSet = new HashSet<Node>(); Node nodeZ = firstNode; /* * This while block will find the first circle node. */ while (true) { hashSet.add(nodeZ); nodeZ = nodeZ.nextNode; if (hashSet.contains(nodeZ)) { break; } } System.out.println("The first circle node is " + nodeZ.data); } else { System.out.println("This is not single circle link"); } } } ///////////////////////////////////////////////////////////////////////////////////////// /** * @author shengshu * */ public class SingleCircleLinkApp { public static void main(String[] args) { Node node6 = new Node("6", null); Node node5 = new Node("5", node6); Node node4 = new Node("4", node5); Node node3 = new Node("3", node4); Node node2 = new Node("2", node3); Node node1 = new Node("1", node2); node6.nextNode = node3; SingleCircleLink singleCircleLink = new SingleCircleLink(node1); singleCircleLink.printFirstCircleNode(singleCircleLink.isSingleCircleLink()); } }