893
技術社區[雲棲]
判斷單鏈是否循環，並且找出第一個循環節點
介紹
判斷單鏈是否循環，並且找出第一個循環節點。
思路
【判斷單鏈是否循環】：如果單鏈是循環的，那麼循環部分就是封閉的。這好比一個田徑運動場，當兩個人跑步時，開始雖然有一定的間距，但他們遲早會相遇的。
順其自然的我們從中抽取一個數學模型，一個是步長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());
}
}
最後更新：2017-04-03 05:39:35