"如何在LinkedList中检测循环/周期"。

这个问题与数据结构更有关。
如果存在循环，我们还可以找到循环的启动节点。

你可能思考的第一个方法可能是：

• 通过每个节点遍历到结束，使用访问的标志跟踪访问的节点。
• 如果找到已访问的节点，则链接列表中有一个循环，如果遍历到结束，则链接列表中没有循环

但上述方法的问题是，在大多数情况下，我们无法更改LinkedList节点的数据结构，因此我们将无法将访问的标志添加到其中。

有效的方法：

对于这个问题的有效方法将是Floyd的循环检测算法，因此本体的步骤将是：

• 使用两个指针fastptr和stropptr并初始化链接列表头部
• 每次迭代中的一个节点将FastPtr移动到两个节点和慢动网。
• 如果fastptr和stropptr在某些迭代时会满足，则LinkedList中存在一个循环。
• 如果FastPtr到达LinkedList的末尾而不会见慢指针，则LinkedList中没有循环(即FastPtr-> Next或者FastPtr-> Next-> Next成为Null)

这个Algo的Java代码将是

public boolean ifLoopExists() {
  Node fastPtr = head;
  Node slowPtr = head;
  while (fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
   if (slowPtr == fastPtr)
    return true;
 
  }
  return false;
 }

以上解决方案适用于O(n)时间复杂度和O(1)空间复杂性。

允许在没有循环的情况下创建链接列表：

允许创建一个名为"linkedlist.java"的Java程序

package org.igi.theitroad;
 
public class LinkedList{
 
	private Node head;
 
	private static class Node {
		private int value;
		private Node next;
 
		Node(int value) {
			this.value = value;
 
		}
	}
 
	public void addToTheLast(Node node) {
 
		if (head == null) {
			head = node;
		} else {
			Node temp = head;
			while (temp.next != null)
				temp = temp.next;
 
			temp.next = node;
		}
	}
 
 
	public void printList() {
		Node temp = head;
		while (temp != null) {
			System.out.format("%d ", temp.value);
			temp = temp.next;
		}
		System.out.println();
	}
 
	public boolean ifLoopExists() {
		Node fastPtr = head;
		Node slowPtr = head;
		while (fastPtr != null && fastPtr.next != null) {
			fastPtr = fastPtr.next.next;
			slowPtr = slowPtr.next;
			if (slowPtr == fastPtr)
				return true;
 
		}
		return false;
	}
 
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		//Creating a linked list
 
		list.addToTheLast(new Node(5));
		list.addToTheLast(new Node(6));
		list.addToTheLast(new Node(7));
		list.addToTheLast(new Node(1));
		list.addToTheLast(new Node(2));
 
 
		list.printList();
 
		//Test if loop existed or not
		System.out.println("Loop existed-->" + list.ifLoopExists());
 
	}
}

逻辑上，我们的链接列表可以表示为：

运行上面的程序，我们将获取以下输出：

5 6 7 1 2 
Loop existed-->false

允许在LinkedList中创建一个循环

现在我们将上次节点连接到NodeWith值7，它将在链接列表中创建循环，因此更改高于Main方法：

public static void main(String[] args) {
		LinkedList list = new LinkedList();
		//Creating a linked list
		Node loopNode=new Node(7);
		list.addToTheLast(new Node(5));
		list.addToTheLast(new Node(6));
		list.addToTheLast(loopNode);
		list.addToTheLast(new Node(1));
		list.addToTheLast(new Node(2));
 
		list.printList();
		//creating a loop
		list.addToTheLast(loopNode);
		//Test if loop existed or not
		System.out.println("Loop existed-->" + list.ifLoopExists());
 
	}

逻辑上我们的LinkedList循环可以表示为：

运行上面的程序，我们将获取以下输出：

5 6 7 1 2 
Loop existed-->true