How does one find a loop in a singly linked list in O(n) time using constant memory? You cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.)

My solution:

int magic = list.size();

for(Node node = list.firstNode(); node.hasNext(); node = node.getNext()) { if(--magic < 0) throw Exception("Loop found"); }

I hope the logic is right... :)

Later! Rex - www.waterlogic.com.sg - advanced real-time visual effects

-- Anonymous, May 29, 2001

Answers

But are you allowed to use Java's linked list, or do you have no information on linked-list size? I unfortunately heard this puzzler before, and there is one solution that does not depend on anything more sophisticated than memory chained together, without any information on how many nodes there are.

If you don't get to use node.size(), you'd actually have to iterate through the list to find the size, and you would just loop forever if the list were circular.

-- Anonymous, May 30, 2001

if (head == null) return false;

for (node = head->next; node; node = node->next) { if (node == head) { return true; } } return false;

-- Anonymous, May 31, 2001

Techinterview is down, so I can't tell if they have an answers page... if you want spoilers, Kuro5hin has a page...

http://www.kuro5hin.org/?op=displaystory&sid=2001/2/1/51055/30558

Unfortunately, the algorithm that checks if node[i] = node[0] (the head node) doesn't work cause the loop could occur anywhere in the list. node[19] could point to node[5], for example, and there's your circularity right there.

-- Anonymous, June 01, 2001

1. Node *p1, *p2; 2. p1 = p2 = list; 3. while (p2 && p1 != p2) { 4. p1 = p1->next; 5. p2 = p2->next; 6. if (p2) p2 = p2->next; } 7. if (p2) return HaveLoop; else return NoLoop;

Hi, your link pointed to this solution, which I think does not work. In line 2, p1 == p2, so the while loop will not run in line 3. So this whole thing fails.

-- Anonymous, June 01, 2001

Yeah, the algorithm he listed is defective; it should've been more rigorous... but the gist is that two points travel down the linked list at different speeds. If they ever meet before one hits the end, the list is circular and there is no end.

It definitely holds true if the speeds are 1 and 2 nodes per iteration. Since we're dealing with a circle, I'm sure that the speeds just have to be relatively prime.

-- Anonymous, June 02, 2001