All Puzzles: Here
Puzzle: 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?
Source: Heard from a fellow student at UC Berkeley in 1996. This used to be a popular interview problem for software engineers in those days.
Solution:
- 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!
- 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”.
- 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.
- 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!
Followup: Consider two linked lists whose tails are joined to give the overall structure a Y-shape. Identify the first common node in these two linked lists in linear time with O(1) additional space and without modifying the two lists.
Your puzzle collections are very instructive. Thanks!
Looks good… :)
Lets call the two lists forming Y shape as “list_m” and the other “list_n”
we can determine the length of the two lists by traversing the lists till the common tail one by one. Lets say the lengths of the two lists come out to be m and n. These two steps will also determine whether the two lists do have a common tail.
case ( m >n )
Take 2 pointer ptr_m and ptr_n pointing at the heads of list_m and list_n respectively . We know that list_m is longer than list_n ( since m>n ) and the difference in the length must in the bifurcated part if the Y shaped list (since the tail portion is common to both the lists). we give a ( m-n ) step headstart to ptr_m ( ptr_m+=(m-n) ) and then in a while loop keep incrementing both ptr_m and ptr_n till condition (ptr_m == ptr_n) is not met . ptr_m or ptr_n is your first common node.
the case ( m <= n ) can be worked out in the same way
To determine the length of the two lists, you have already traversed the whole list. how does (m-n) headstart help in this case?
We can as well chk for the common point in the first traversal itself..
thr should be a better solution..
I think the time complexity comes out be m+n+2(m-n)= linear time plus O(1). Seems to me a perfectly good solution..