Classical Cyclic Loop detection in Linked List

Discussion
,
1

Let’s start with one of the classic Linked List problems:

LinkedList-Loop-Detect

Given a linked list, determine if it has a cycle in it.

You might have come up with the solutions like

  1. Using the hash table

  2. Using the two-pointer technique.

Try to think it over by yourself before jumping to the more efficient two-pointer solution

i.e. using two pointers with different speed in a linked list:

a. If there is no cycle, the fast pointer will stop at the end of the linked list.
b. If there is a cycle, the fast pointer will eventually meet with the slow pointer.

So the only remaining problem is:

What should be the proper speed for the two pointers?

2

I don’t really get the point of this post.

Is it a question to the community or is it a fun quiz?

Both are valid reasons, but I find the problem to be improperly formulated: The underlying data structure is rather unclear.

The two search algorithms are not well-defined, so it’s hardly possible to compare them in any meaningful way.

Important question: Do we know the total number of nodes?

3 Likes