3

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?

skydoor
  • 25,218
  • 52
  • 147
  • 201

3 Answers3

4

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.

Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
Anon.
  • 58,739
  • 8
  • 81
  • 86
1

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.

No Refunds No Returns
  • 8,092
  • 4
  • 32
  • 43
  • 1
    With little extra de-referencing, we can avoid traversing the entire list again to reset the nodes. E.g. have two bool variables visited1 and visited2. Initialize visited1=false and visted2=true. Before starting the check, all nodes point to visited1 and visited1=false. Now, for each visited node, make it to point to visited2. If you encounter a node whose visited link points to "true" then there exist a loop. Now for resetting the link list, just toggle the values of visited1 and visted2. – LionHeart Nov 28 '10 at 04:38
1

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.

aalmos
  • 161
  • 7