CODEWITHSUNDEEP
linked-list
skydoor
skydoor

Reputation: 25868

find whether a loop in a linked list without two pointers

find whether there is a loop in a linked list. Do you have other ways instead of using a quick pointer and a slow pointer?

Upvotes: 3

Views: 2394

Answers (3)

aalmos
aalmos

Reputation: 171

As the previous solutions say, you have to mark the node visited somehow. Actually in every singly linked list node you have at least 3 bits extra space (in the 'next' pointer), since all memory addresses are the multiple of 8. So you can do a bit of a hack, and set for example the last bit of the 'next' pointer to 1. Note that when advancing on the linked list you have to mask out the last bit of the 'next' pointer to have a valid memory address.

Upvotes: 1

Anon.
Anon.

Reputation: 59973

There are a variety of ways you can do this, depending on your situation.

  1. Add each node to a Set of some kind when you reach it. Go through the list until you reach the end or find a node already in the Set.

  2. If you have spare space in the nodes, you can mark each node as "visited" or not and walk the list until you find one you've already marked.

These, of course, all have downsides (like high memory use) or situations where they're not usable, while the two-pointer method doesn't use extra memory and is applicable pretty much everywhere.

Upvotes: 4

No Refunds No Returns
No Refunds No Returns

Reputation: 8336

You will have to mark each node as visited and detected an already visited node that has your mark. Problem is what to mark it with so you don't have to run the list to reset everything before or after.

Upvotes: 1

Related Questions