Floyd's cycle-finding algorithm

Question

I'm trying to find this algorithm on C++ in .NET but can't, I found this one:

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

but doesn't seem to be right, or am I wrong? How can I actually prove that my hare will meet tortoise at the end? Thanks in advance for any explanation how exactly does it work and proof

EDITED

About this solution, I found that in regular algorithm they use only one fast iterator but here they use two, why?

score 3 · Accepted Answer · answered Oct 07 '10 at 10:42

3

The idea in the code you've found seems fine. Two fast iterators are used for convenience (although I'm positive such kind of 'convenience', like putting a lot of 'action' in the condition of while loop, should be avoided). You can rewrite it in more readable way with one variable:

while (fastNode && fastNode.next()) {
    if (fastNode.next() == slowNode || fastNode.next().next() == slowNode) {
        return true;
    }
    fastNode = fastNode.next().next();
    slowNode = slowNode.next();
}

answered Oct 07 '10 at 10:42

Nikita Rybak

67,365
22
157
181

the problem with `fastNode.next().next()` is that the first next may return null – Itay Karo Oct 07 '10 at 11:34
@Itay nope, it's checked in the loop condition – Nikita Rybak Oct 07 '10 at 11:43

Fred Foo · Answer 2 · 2010-10-07T11:39:11.310

The algorithm is correct. Proof:

The case of no cycle is trivial: the hare will find the end of the list.

So, there's a cycle, and the hare enters it, running around like crazy. Eventually, the tortoise reaches the first node of the cycle. From this point on, both necessarily stay in the cycle: the only way they can go from a node is to the next node, which eventually leads back to the first node of the cycle. (Draw a picture of the list/graph to convince yourself.)

Since the hare moves faster, it will eventually catch up with the tortoise. Depending on the length of the cycle and the number of nodes traversed before entering it (whether they are odd or even is what matters, so there are four cases), this may happen after an odd or an even number of steps. That's why the hare should check both its current node and the next node for the tortoise's presence. (The example code uses two pointers to achieve this, though that's not really necessary.)

For a more formal proof, check out this Wikipedia page.

score 0 · Answer 3 · answered Oct 07 '10 at 10:41

This algorithm will find a cycle in a linked list.
one fast node can be used instead:

 function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode = startNode;
  while (slowNode && fastNode = fastNode.next() && fastNode = fastNode.next()){
    if (slowNode == fastNode) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Floyd's cycle-finding algorithm

EDITED

3 Answers3

Linked