CODEWITHSUNDEEP
algorithmlinked-list
PDN
PDN

Reputation: 791

Follow up on detecting loop in linked list

So there are several questions on how to detect a loop in a linked list. Here is one example. My question is, why do all these algorithms use two pointers? Couldn't you just loop through with one pointer and mark the nodes as visited, and when you come to a node you've already visited or reach the end of the linked list (next = null), then you know there is no loop?

Upvotes: 0

Views: 42

Answers (1)

Gareth McCaughan
Gareth McCaughan

Reputation: 19971

It's because to

mark the nodes as visited

you need either extra space in the nodes themselves to do it, or an auxiliary data structure whose size will increase with that of the list, whereas the two-pointer solutions require only enough extra space for one more pointer.

[EDITED to add:] ... And, perhaps, also because the two-pointer solutions are clever and people like clever solutions to things.

Upvotes: 2

Related Questions