Given the head of a linked list, find if it contains a loop or not, in linear time. Can you accomplish it with only O(1) extra space? Can you do it without modifying the list in any way?

Heard from a fellow student at UC Berkeley in 1996. This used to be a popular interview problem for software engineers in those days.

1. Hash Table: Traverse the list and store the pointers in a hash table. As soon as you discover a collision, you've discovered a loop!
2. List Reversal: Traverse the list and start reversing it. If there is a loop, you shall revisit the head again. However, the "loop" in the list has been reversed -- to fix that, traverse the list again, reversing the pointers! When I posted the following solution to a newsgroup many years ago, somebody pointed out that it is a haiku :) "Start reversing the list. If you hit the head, there's a loop".
3. Pointer Marking: In practice, linked lists are implemented using C structs with at least a pointer; such a struct in C shall be 4-byte aligned. So the least significant two bits are zeros. While traversing the list, you may 'mark' a pointer as traversed by flipping the least significant bit. A second traversal is for clearing these bits.
4. Two Pointers: Start with two pointers pointing to the head. At each step, the 'slower' pointer moves forward only one step and the 'faster' pointer moves forward two steps. If the faster pointer overtakes the slower pointer at any point of time, we have discovered a loop! For more algorithmic ideas, check out Wikipedia article on Cycle Detection.

1) A linked list with a loop has the shape of a "lollipop" with a stick and a cycle. Can you identify the lengths of both the stick and the cycle in linear time using only O(1) extra space?

2) Consider two linked lists whose tails are joined to give the overall structure a Y-shape. Can you identify the first common node in these two linked lists in linear time with O(1) additional space and without modifying the two lists?