Stack Overflow
Stack Overflow

Questions tagged [floyd-cycle-finding]

For detecting the presence of cycle in linked list.

Also named as tortoise and the hare algorithm. The algorithm is named for Robert W. Floyd, who was credited with its invention by Donald Knuth.

It also finds out the start of the loop in the linked list.

44 questions
201
votes
23 answers

How does finding a cycle start node in a cycle linked list work?

I understand that Tortoise and Hare's meeting concludes the existence of a loop, but how does moving tortoise to the beginning of linked list while keeping the hare at the meeting place, followed by moving both one step at a time make them meet at…
Passionate programmer
  • 5,748
  • 10
  • 39
  • 43
81
votes
10 answers

Why increase pointer by two while finding loop in linked list, why not 3,4,5?

I had a look at question already which talk about algorithm to find loop in a linked list. I have read Floyd's cycle-finding algorithm solution, mentioned at lot of places that we have to take two pointers. One pointer( slower/tortoise ) is…
GG.
  • 2,835
  • 5
  • 27
  • 34
45
votes
3 answers

Linked list loop detection algorithm

I read some interview question online about how would you find if there's a loop in a linked list, and solution (Floyd's cycle-finding algorithm) is to have two pointers, one is 2x faster than the other, and check if they meet again. My question is:…
Derek Li
  • 3,089
  • 2
  • 25
  • 38
15
votes
4 answers

Cycle detection in linked list with the Hare and Tortoise approach

I understand that in order to detect a cycle in a linked list I can use the Hare and Tortoise approach, which holds 2 pointers (slow and fast ones). However, after reading in wiki and other resources, I do not understand why is it guaranteed that…
Meir
  • 1,691
  • 2
  • 14
  • 15
8
votes
1 answer

How to implement Floyd's Hare and Tortoise algorithm in Agda?

I want to translate the following Haskell code into Agda: import Control.Arrow (first) import Control.Monad (join) safeTail :: [a] -> [a] safeTail [] = [] safeTail (_:xs) = xs floyd :: [a] -> [a] -> ([a], [a]) floyd xs [] = ([],…
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
8
votes
5 answers

How can we find the starting node of a loop in link list?

According to the Floyd's cycle finding algorithm, the point where tortoise and hare meets explains the circular nature in the link list. To find the starting node in the cycle we initialize tortoise pointer to head of the list and starts…
som
  • 481
  • 1
  • 4
  • 9
6
votes
3 answers

linked list loop - cycle start element and list length

I read about loop in linked list detection algorithm and I doubt 1) How to detect the "meeting element". For example, in the follow case - how to detect that the meeting is at the 3nd element? 2) How to detect the list's length (in case above -…
URL87
  • 10,667
  • 35
  • 107
  • 174
6
votes
4 answers

Detect period of unknown source

How to detect repeating digits in an infinite sequence? I tried Floyd & Brent detection algorithm but come to nothing... I have a generator that yields numbers ranging from 0 to 9 (inclusive) and I have to recognize a period in it. Example test…
rubik
  • 8,814
  • 9
  • 58
  • 88
5
votes
3 answers

Floyd's cycle-finding algorithm

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()…
rookie
  • 7,723
  • 15
  • 49
  • 59
4
votes
2 answers

Floyd's cycle finding algorithm - Need for two pointers?

I was going through Floyd's cycle finding algorithm today and had a doubt. Why would he need two pointers and move them at different speeds? He can instead create two pointers keep one static and compare the pointer of it with another pointer,…
Viswanath Kuchibhotla
  • 171
  • 5
3
votes
2 answers

Floyd algorithm - Cycle Detection - not terminating for the example

Can someone please explain Floyd algorithm with this example. It is not terminating for me and is the algorithm implemented complete ?. Is something wrong with my code? Code is as follows: Node* FindLoopBegin(Node *head){ Node *slowptr =…
Vishnu
  • 479
  • 1
  • 3
  • 14
2
votes
2 answers

Question about logic of removing loop in linked list

Below is the code after finding that loop exists in the list using Floyd's slow fast algorithm. How can we be sure that begin and tortoise will meet at the beginning of the loop? Node begin = head; tortoise = tortoise.next; while (begin !=…
Vimal
  • 77
  • 1
  • 9
2
votes
0 answers

show minimum cycles on a undirected graph using Floyd-Warshall

I'm having some problems with this. First, i used Floyd-warshall to show all min cycles on a directed graph and it worked, but then I tried using it with undirected graph and it doesn't work like I need. For example, lets say I have this graph: INF …
Sage Harpuia
  • 348
  • 2
  • 13
2
votes
0 answers

Floyd’s Cycle-Finding Algorithm

All the documentation I read on the subject explain the algorithm with a starting point outside the loop. What if my linked list is just a giant loop and my starting point is right in the middle ??? How the algorithm will handle that ? The turtoise…
user2631297
  • 21
  • 1
2
votes
3 answers

Floyd's algorithm for finding a cycle in a linkedlist, how to prove that it will always work

I understand the concept of Floyd's algorithm for cycle detection. It concludes that if the Tortoise travels twice as fast as the Hare, and if the Tortoise has a head start of k meters in a loop, the Tortoise and the Hare will meet k meters before…
mirage1s7
  • 277
  • 1
  • 5
  • 10
1
2 3