This one is old school: we're dealing with pointers and very limited memory. Here's the set up:
You are given a pointer to the head of a linked list. Your job is to figure out if the linked list has a cycle (i.e. one of the nodes has a next pointer that points back to some earlier node in the list). The trick is that you only have enough memory on the stack for two node pointers. How do you do it?
I got asked this in a tech intterview as a "bonus question" and it drove me nuts for the better part of an hour. The answer is pretty simple but a little hard to see.
Slashdot Mirror
This one is old school: we're dealing with pointers and very limited memory. Here's the set up:
You are given a pointer to the head of a linked list. Your job is to figure out if the linked list has a cycle (i.e. one of the nodes has a next pointer that points back to some earlier node in the list). The trick is that you only have enough memory on the stack for two node pointers. How do you do it?
I got asked this in a tech intterview as a "bonus question" and it drove me nuts for the better part of an hour. The answer is pretty simple but a little hard to see.
Obviously, the cycles have absconded with the socks that go missing from the wash.