1

I read the solution for the question how to check if linked list is circular.

for: a->b->c->a : TRUE

for: a->b->c->null : FALSE

The solution uses faster and slower pointers. The faster jumps 2 cells each time and the slower goes one cell at a time. If the faster pointer reach NULL then it's false, if the slower meets the faster then its true.

What i don't understand is who grantee that both pointers will meet? if the list is of 10 millions cells, how can you be sure they will meet? what if both passing through endlessly on the list and never meet?

I know that this solution is correct but everywhere i looked there is only explanation what the code does or examples.. nowhere i could find a proof that this actually works in every case.

2 Answers2

2

The key observation is that after each step the distance between the two pointers grows by one (one pointer moves by one step, the other pointer moves by two steps).

If the list is cyclical, and the cycle is n elements long, the two pointers are guaranteed to point to the same element when (1) they have both entered the cycle, and (2) the distance between them is a multiple of n.

  1. Since the pointers start from the same element, if the list is cyclical, they will both enter the cycle eventually. Obviously once in the cycle, they will stay in the cycle forever.
  2. Once the pointer is in a cycle of size n, moving forward (or backwards) by n elements is a no-op. Starting from element x and making n steps takes the pointer back to the element x. From the initial observation we know that the distance between the two pointers is growing by one in each step. At some point the distance between the two pointers is a multiple of n, in which point the pointers are pointing to the same element.
Krzysztof Kozielczyk
  • 5,887
  • 37
  • 28
1

If a circular list has 10,000,000 entries and one pointer is 10,000,000 places past the other pointer, then they're equal.

The algorithm you described will also discover if the list is ρ-shaped as well as circular shaped, because both pointers will eventually reach the circular region. If the only possibilities were a list that ends and a list that was a circle, then you could just step one pointer along the list until it either reached null or it was equal to the head.

These three shapes (-, o, and ρ) are the only three shapes that a (nonempty) singly-linked list can have: if you start at the head and iterate through, either you will reach an end or you will reach an element you've already visited. If you revisit the head you get an o-shape, and if you revisit somewhere else you get a ρ-shape. Thus, being able to handle all three shapes ensures your algorithm will finish.

(In the above, I've defined the "list" to be the set of nodes you can reach starting from the head and iterating. These nodes could potentially be part of a larger, more complicated graph.)