0

Is there a way to check if a single-linked list contains cycles for linear time without copying and modifying the list?

I thought we could try to sort this list topologically. If cannot there is somr cycle... But it seems it's not gonna work.

St.Antario
  • 26,175
  • 41
  • 130
  • 318
  • 4
    Use classical solutions with fast and slow iterator. It can even tell you where the loop starts – Teivaz Apr 01 '17 at 13:07
  • You could do a dfs and if you reach a visited node then it's either a cross edge or a back edge. To distinguish back edges, use "colors" to determine whether you are currently processing a node (recursing on its children) or have completed its processing recursed back up to it). Then all back edges are cycles. – Jeremy Fisher Apr 01 '17 at 13:14
  • 3
    Possible duplicate of [How to detect a loop in a linked list?](http://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list) – Paul Hankin Apr 01 '17 at 14:04

2 Answers2

1

You can do it in constant space without altering the array.

The method is known as Floyd's cycle-finding algorithm. It is based on the idea of going through the list with two pointers moving at different speeds. Eventually, if and only if the list contains a cycle, the pointers will meet. Also, the algorithm finds the point where the loop starts. Check the provided link for more details.

pkacprzak
  • 5,537
  • 1
  • 17
  • 37
0

As suggested in the comment, you can use fast and slow iterator solution.

Key insight:

The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, x(i) = x(i + kλ), where λ is the length of the loop to be found and μ is the index of the first element of the cycle. In particular, i = kλ ≥ μ, if and only if x(i) = x(2i). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value xμ in the sequence, using the fact that λ divides ν and therefore that x(μ) = x(μ + v). Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which x(μ + λ) = x(μ).

Reference Link : Floyd's Tortoise and Hare

รยקคгรђשค
  • 1,919
  • 1
  • 10
  • 18