本文為原創(chuàng)文章然痊，轉載請注明出處至朗，謝謝你……
喜歡java并發(fā)編程的請加群：736156823
開始-->
判斷鏈表中是否有環(huán)。
通過改動算法剧浸，可以達到去除鏈表中環(huán)的目的（本文章不提供改動）锹引。
public class FindLoop {
private FindLoop() {
}
public static final FindLoop create() {
return new FindLoop();
}
public final LoopStructure getLoop(Node head) {
if (null == head) {
return noLoop();
}
Node temp = head;
if (null == temp.getNext()) {
return noLoop();
}
Node slow = head;
Node fast = head;
boolean has = false;
for (; null != fast.getNext() && null != fast.getNext().getNext(); ) {
slow = slow.getNext();
fast = fast.getNext().getNext();
if (slow == fast) {
has = true;
break;
}
}
if (has) {
int count = 0;
Node loopLenFlag = slow;
// 處理長度遠大于環(huán)長度的情況
boolean meetLoopLenFlag = false;
Node endFlag = fast;
slow = head;
for (; fast != slow; ) {
slow = slow.getNext();
fast = fast.getNext();
if (endFlag.getNext() != fast) {
endFlag = endFlag.getNext();
}
if (fast != loopLenFlag) {
if (!meetLoopLenFlag) {
count++;
}
} else {
if (!meetLoopLenFlag) {
count++;
meetLoopLenFlag = true;
}
}
}
Node start = slow;
Node end = endFlag;
if (!meetLoopLenFlag) {
for (; fast != loopLenFlag; ) {
fast = fast.getNext();
count++;
}
}
return LoopStructure.create(start, end, count, true);
} else {
return noLoop();
}
}
private final LoopStructure noLoop() {
return LoopStructure.create(null, null, 0, false);
}
public static final void main(String args[]) {
FindLoop findLoop = FindLoop.create();
Node loop = CreateList.create().buildLoop(1189000, 78);
LoopStructure structure = findLoop.getLoop(loop);
System.out.println("loop is in list=" + structure.isHasLoop());
System.out.println("loop length=" + structure.getLoopLength());
System.out.println("loop start data=" + structure.getStart().getDate());
System.out.println("loop end data=" + structure.getEnd().getDate());
}
private static final class LoopStructure {
// 環(huán)的開始節(jié)點
private final Node start;
// 環(huán)的結束節(jié)點
private final Node end;
// 環(huán)的長度
private final int loopLength;
// 是否存在環(huán)
private final boolean hasLoop;
private LoopStructure(Node start, Node end, int loopLength, boolean hasLoop) {
this.start = start;
this.end = end;
this.loopLength = loopLength;
this.hasLoop = hasLoop;
}
public static final LoopStructure create(Node start, Node end, int loopLength, boolean hasLoop) {
return new LoopStructure(start, end, loopLength, hasLoop);
}
public Node getStart() {
return start;
}
public Node getEnd() {
return end;
}
public int getLoopLength() {
return loopLength;
}
public boolean isHasLoop() {
return hasLoop;
}
}
}
[Floyd's cycle-finding algorithm]
(https://stackoverflow.com/questions/3880735/floyds-cycle-finding-algorithm)
輔助工具類1：節(jié)點
public class Node {
private Node next;
private int date;
private Node() {
}
public static final Node create() {
return new Node();
}
public void setNext(final Node next) {
this.next = next;
}
public Node getNext() {
return next;
}
public int getDate() {
return date;
}
public void setDate(int date) {
this.date = date;
}
@Override
public String toString() {
return "Node{" +
"date=" + date +
'}';
}
}
輔助工具類2：鏈表創(chuàng)建類
public class CreateList {
private CreateList() {
}
public static final CreateList create() {
return new CreateList();
}
public final Node buildNormal(int length) {
return build(length).getHead();
}
private final HeadTail build(int length) {
final Node head = Node.create();
Node current = head;
for (int i = 0; i < length; i++) {
Node node = Node.create();
node.setDate(i + 1);
current.setNext(node);
current = node;
}
final HeadTail ht = HeadTail.create(head, current);
return ht;
}
public final Node buildLoop(int listLength, int loopLength) {
if (listLength < 0) {
throw new IllegalArgumentException();
}
if (listLength == 0) {
return Node.create();
}
if (loopLength <= 0) {
return buildNormal(listLength);
}
if (loopLength > listLength) {
throw new IllegalArgumentException();
}
HeadTail ht = build(listLength);
Node head = ht.getHead();
Node tail = ht.getTail();
if (loopLength == listLength) {
tail.setNext(head.getNext());
} else {
Node temp = head;
int dur = listLength - loopLength;
for (int i = 0; i < dur; i++) {
temp = temp.getNext();
}
tail.setNext(temp.getNext());
}
return head;
}
private static final class HeadTail {
private final Node head;
private final Node tail;
private HeadTail(final Node head, final Node tail) {
this.head = head;
this.tail = tail;
}
public static final HeadTail create(final Node head, final Node tail) {
return new HeadTail(head, tail);
}
public Node getHead() {
return head;
}
public Node getTail() {
return tail;
}
}
}
運行截圖
image.png
喜歡java并發(fā)編程的請加群：736156823
有問題歡迎指正，這是新鮮出爐的
結束-->
本文為原創(chuàng)文章辛蚊，轉載請注明出處粤蝎，謝謝你……
