1. Introduction
1.介绍
A singly linked list is a sequence of connected nodes ending with a null reference. However, in some scenarios, the last node might point at a previous node – effectively creating a cycle.
单链表是一个以null引用结束的连接节点的序列。然而，在某些情况下，最后一个节点可能指向前一个节点–有效地创造了一个循环。
In most cases, we want to be able to detect and be aware of these cycles; this article will focus on exactly that – detecting and potentially removing cycles.
在大多数情况下，我们希望能够检测并意识到这些周期；本文将关注的正是这一点–检测并可能消除周期。
2. Detecting a Cycle
2.检测一个周期
Let’s now explore a couple of algorithms for detecting cycles in linked lists.
现在让我们来探讨一下检测链表中的循环的几种算法。
2.1. Brute Force – O(n^2) Time Complexity
2.1.蛮力–O(n^2)时间复杂度
With this algorithm, we traverse the list using two nested loops. In the outer loop, we traverse one-by-one. In the inner loop, we start from the head and traverse as many nodes as traversed by outer loop by that time.
通过这种算法，我们使用两个嵌套的循环来遍历列表。在外循环中，我们逐一遍历。在内循环中，我们从头部开始，遍历与外循环所遍历的相同数量的节点。
If a node that is visited by the outer loop is visited twice by the inner loop, then a cycle has been detected. Conversely, if the outer loop reaches the end of the list, this implies an absence of cycles:
如果一个被外循环访问的节点被内循环访问了两次，那么就检测到了一个循环。反之，如果外循环到达了列表的末端，这意味着没有循环。
public static <T> boolean detectCycle(Node<T> head) {
if (head == null) {
return false;
}
Node<T> it1 = head;
int nodesTraversedByOuter = 0;
while (it1 != null && it1.next != null) {
it1 = it1.next;
nodesTraversedByOuter++;
int x = nodesTraversedByOuter;
Node<T> it2 = head;
int noOfTimesCurrentNodeVisited = 0;
while (x > 0) {
it2 = it2.next;
if (it2 == it1) {
noOfTimesCurrentNodeVisited++;
}
if (noOfTimesCurrentNodeVisited == 2) {
return true;
}
x--;
}
}
return false;
}The advantage of this approach is that it requires a constant amount of memory. The disadvantage is that the performance is very slow when large lists are provided as an input.
这种方法的优点是它需要恒定的内存量。缺点是，当提供大型列表作为输入时，性能非常缓慢。
2.2. Hashing – O(n) Space Complexity
2.2.哈希–O(n)空间复杂度
With this algorithm, we maintain a set of already visited nodes. For each node, we check if it exists in the set. If not, then we add it to the set. The existence of a node in the set means we have already visited the node and brings forward the presence of a cycle in the list.
通过这种算法，我们维护一个已经访问过的节点的集合。对于每个节点，我们检查它是否存在于这个集合中。如果不存在，那么我们就把它添加到这个集合中。集合中的一个节点的存在意味着我们已经访问过该节点，并在列表中提出了一个周期的存在。
When we encounter a node which already exists in the set, we’d have discovered the beginning of the cycle. After discovering this, we can easily break the cycle by setting the next field of the previous node to null, as demonstrated below:
当我们遇到一个已经存在于集合中的节点时，我们就会发现循环的开始。发现这一点后，我们可以通过将前一个节点的next字段设置为null来轻松打破这个循环，如下图所示。
public static <T> boolean detectCycle(Node<T> head) {
if (head == null) {
return false;
}
Set<Node<T>> set = new HashSet<>();
Node<T> node = head;
while (node != null) {
if (set.contains(node)) {
return true;
}
set.add(node);
node = node.next;
}
return false;
}In this solution, we visited and stored each node once. This amounts to O(n) time complexity and O(n) space complexity, which, on average, is not optimal for large lists.
在这个解决方案中，我们对每个节点访问和存储一次。这相当于O(n)的时间复杂度和O(n)的空间复杂度，平均来说，这对大型列表来说不是最佳的。
2.3. Fast and Slow Pointers
2.3.快速和慢速指针
The following algorithm for finding cycles can best be explained using a metaphor.
以下寻找周期的算法可以用一个比喻来解释，。
Consider a race track where two people are racing. Given that the speed of the second person is double that of the first person, the second person will go around the track twice as fast as the first and will meet the first person again at the beginning of the lap.
考虑一个有两个人在比赛的赛道。鉴于第二个人的速度是第一个人的两倍，第二个人将以第一个人两倍的速度绕过赛道，并将在一圈开始时再次遇到第一个人。
Here we use a similar approach by iterating through the list simultaneously with a slow iterator and a fast iterator (2x speed). Once both iterators have entered a loop, they will eventually meet at a point.
这里我们使用类似的方法，用一个慢速迭代器和一个快速迭代器（2倍速度）同时迭代列表。一旦两个迭代器都进入一个循环，它们最终会在一个点上相遇。
Hence, if the two iterators meet at any point, then we can conclude that we have stumbled upon a cycle:
因此，如果这两个迭代器在任何一点上相遇，那么我们可以得出结论，我们已经偶然发现了一个循环。
public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
if (head == null) {
return new CycleDetectionResult<>(false, null);
}
Node<T> slow = head;
Node<T> fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return new CycleDetectionResult<>(true, fast);
}
}
return new CycleDetectionResult<>(false, null);
}Where CycleDetectionResult is a convenience class to hold the result: a boolean variable which says whether cycle exists or not and if exists, then this also contains a reference to the meeting point inside the cycle:
其中CycleDetectionResult是一个方便的类，用来保存结果：一个boolean变量，它表示循环是否存在，如果存在，那么它还包含一个对循环内的汇合点的引用。
public class CycleDetectionResult<T> {
boolean cycleExists;
Node<T> node;
}This method is also known as the ‘The Tortoise and The Hare Algorithm’ or ‘Flyods Cycle-Finding Algorithm’.
这种方法也被称为 “龟兔赛跑算法 “或 “Flyods循环寻找算法”。
3. Removal of Cycles from a List
3.从列表中删除周期
Let’s have a look at a few methods for removing cycles. All these methods assume that the ‘Flyods Cycle-Finding Algorithm’ was used for cycle detection and build on top of it.
让我们来看看去除周期的几种方法。所有这些方法都假定 “Flyods Cycle-Finding Algorithm “被用于周期检测，并建立在它之上。
3.1. Brute Force
3.1.蛮力
Once the fast and the slow iterators meet at a point in the cycle, we take one more iterator (say ptr) and point it to the head of the list. We start iterating the list with ptr. At each step, we check if ptr is reachable from the meeting point.
一旦快迭代器和慢迭代器在循环中的某一点相遇，我们再取一个迭代器（比如ptr）并将其指向列表的头部。我们用ptr开始迭代列表。在每一步，我们检查ptr是否可以从相遇点到达。
This terminates when ptr reaches the beginning of the loop because that is the first point when it enters the loop and becomes reachable from the meeting point.
当ptr到达循环的起点时，这就终止了，因为那是它进入循环的第一点，并成为可以从汇合点到达的地方。
Once the beginning of the loop (bg) is discovered, then it is trivial to find the end of the cycle (node whose next field points to bg). The next pointer of this end node is then set to null to remove the cycle:
一旦发现了循环的起点（bg），那么找到循环的终点（下一个字段指向bg的节点）就很简单了。然后，这个结束节点的下一个指针被设置为null，以删除循环。
public class CycleRemovalBruteForce {
private static <T> void removeCycle(
Node<T> loopNodeParam, Node<T> head) {
Node<T> it = head;
while (it != null) {
if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
Node<T> loopStart = it;
findEndNodeAndBreakCycle(loopStart);
break;
}
it = it.next;
}
}
private static <T> boolean isNodeReachableFromLoopNode(
Node<T> it, Node<T> loopNodeParam) {
Node<T> loopNode = loopNodeParam;
do {
if (it == loopNode) {
return true;
}
loopNode = loopNode.next;
} while (loopNode.next != loopNodeParam);
return false;
}
private static <T> void findEndNodeAndBreakCycle(
Node<T> loopStartParam) {
Node<T> loopStart = loopStartParam;
while (loopStart.next != loopStartParam) {
loopStart = loopStart.next;
}
loopStart.next = null;
}
}Unfortunately, this algorithm also performs poorly in case of large lists and large cycles, because we’ve to traverse the cycle multiple times.
不幸的是，这种算法在大列表和大循环的情况下也表现不佳，因为我们必须多次遍历循环。
3.2. Optimized Solution – Counting the Loop Nodes
3.2.优化的解决方案 – 计算循环节点
Let’s define a few variables first:
让我们先定义几个变量。
- n = the size of the list
- k = the distance from the head of the list to the start of the cycle
- l = the size of the cycle
We have the following relationship between these variables:
k + l = n
我们在这些变量之间有如下关系：
k + l = n
We utilize this relationship in this approach. More particularly, when an iterator that begins from the start of the list, has already traveled l nodes, then it has to travel k more nodes to reach the end of the list.
我们在这个方法中利用了这种关系。更具体地说，当一个从列表开始的迭代器已经走过了l个节点，那么它必须再走过k个节点才能到达列表的结尾。
Here’s the algorithm’s outline:
以下是该算法的大纲。
- Once fast and the slow iterators meet, find the length of the cycle. This can be done by keeping one of the iterators in place while continuing the other iterator (iterating at normal speed, one-by-one) till it reaches the first pointer, keeping the count of nodes visited. This counts as l
- Take two iterators (ptr1 and ptr2) at the beginning of the list. Move one of the iterator (ptr2) l steps
- Now iterate both the iterators until they meet at the start of the loop, subsequently, find the end of the cycle and point it to null
This works because ptr1 is k steps away from the loop, and ptr2, which is advanced by l steps, also needs k steps to reach the end of the loop (n – l = k).
这是因为ptr1离循环还有k步，而ptr2，前进了l步，也需要k步来到达循环的终点（n-l=k）。
And here’s a simple, potential implementation:
这里有一个简单的、潜在的实施方案。
public class CycleRemovalByCountingLoopNodes {
private static <T> void removeCycle(
Node<T> loopNodeParam, Node<T> head) {
int cycleLength = calculateCycleLength(loopNodeParam);
Node<T> cycleLengthAdvancedIterator = head;
Node<T> it = head;
for (int i = 0; i < cycleLength; i++) {
cycleLengthAdvancedIterator
= cycleLengthAdvancedIterator.next;
}
while (it.next != cycleLengthAdvancedIterator.next) {
it = it.next;
cycleLengthAdvancedIterator
= cycleLengthAdvancedIterator.next;
}
cycleLengthAdvancedIterator.next = null;
}
private static <T> int calculateCycleLength(
Node<T> loopNodeParam) {
Node<T> loopNode = loopNodeParam;
int length = 1;
while (loopNode.next != loopNodeParam) {
length++;
loopNode = loopNode.next;
}
return length;
}
}Next, let’s focus on a method in which we can even eliminate the step of calculating the loop length.
接下来，让我们关注一种方法，在这种方法中，我们甚至可以取消计算循环长度的步骤。
3.3. Optimized Solution – Without Counting the Loop Nodes
3.3.优化的解决方案 – 不计算循环节点
Let’s compare the distances traveled by the fast and slow pointers mathematically.
让我们从数学上比较一下快指针和慢指针所走的距离。
For that, we need a few more variables:
为此，我们还需要一些变量。
- y = distance of the point where the two iterators meet, as seen from the beginning of the cycle
- z = distance of the point where the two iterators meet, as seen from the end of the cycle (this is also equal to l – y)
- m = number of times the fast iterator completed the cycle before the slow iterator enters the cycle
Keeping the other variables same as defined in the previous section, the distance equations will be defined as:
保持其他变量与上一节中的定义相同，距离方程将被定义为。
- Distance traveled by slow pointer = k (distance of cycle from head) + y (meeting point inside cycle)
- Distance traveled by fast pointer = k (distance of cycle from head) + m (no of times fast pointer completed the cycle before slow pointer enters) * l (cycle length) + y (meeting point inside cycle)
We know that distance traveled by the fast pointer is twice that of the slow pointer, hence:
我们知道，快指针所走的距离是慢指针的两倍，因此。
k + m * l + y = 2 * (k + y)
k + m * l + y = 2 * (k + y)
which evaluates to:
其中评估为。
y = m * l – k
y = m * l – k。
Subtracting both sides from l gives:
从l中减去两边，得到。
l – y = l – m * l + k
l – y = l – m * l + k 。
or equivalently:
或等价的。
k = (m – 1) * l + z (where, l – y is z as defined above)
k = (m – 1) * l + z (其中，l – y是上面定义的z)
This leads to:
这就导致了。
k = (m – 1) Full loop runs + An extra distance z
k = (m – 1) 全循环运行 + 一个额外的距离z。
In other words, if we keep one iterator at the head of the list and one iterator at the meeting point, and move them at the same speed, then, the second iterator will complete m – 1 cycles around the loop and meet the first pointer at the beginning of the cycle. Using this insight we can formulate the algorithm:
换句话说，如果我们把一个迭代器放在列表的头部，一个迭代器放在交汇点，并以相同的速度移动它们，那么，第二个迭代器将完成m – 1循环，并在循环的起点与第一个指针相遇。利用这一洞察力，我们可以制定算法。
- Use ‘Flyods Cycle-Finding Algorithm’ to detect the loop. If loop exists, this algorithm would end at a point inside the loop (call this the meeting point)
- Take two iterators, one at the head of the list (it1) and one at the meeting point (it2)
- Traverse both iterators at the same speed
- Since the distance of the loop from head is k (as defined above), the iterator started from head would reach the cycle after k steps
- In k steps, iterator it2 would traverse m – 1 cycles of the loop and an extra distance z. Since this pointer was already at a distance of z from the beginning of the cycle, traversing this extra distance z, would bring it also at the beginning of the cycle
- Both the iterators meet at the beginning of the cycle, subsequently, we can find the end of the cycle and point it to null
This can be implemented:
这一点是可以实现的。
public class CycleRemovalWithoutCountingLoopNodes {
private static <T> void removeCycle(
Node<T> meetingPointParam, Node<T> head) {
Node<T> loopNode = meetingPointParam;
Node<T> it = head;
while (loopNode.next != it.next) {
it = it.next;
loopNode = loopNode.next;
}
loopNode.next = null;
}
}This is the most optimized approach for detection and removal of cycles from a linked list.
这是检测和去除链表中的周期的最优化方法。
4. Conclusion
4.结论
In this article, we described various algorithms for detecting a cycle in a list. We looked into algorithms with different computing time and memory space requirements.
在这篇文章中，我们描述了检测一个列表中的周期的各种算法。我们研究了具有不同计算时间和内存空间要求的算法。
Finally, we also showed three methods to remove a cycle, once it is detected using the ‘Flyods Cycle-Finding Algorithm’.
最后，我们还展示了三种去除循环的方法，一旦使用 “Flyods循环寻找算法 “检测到循环，就可以将其去除。
The full code example is available over on Github.
完整的代码示例可在Github上获得，。