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) 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?