2 ms·
Iterate over the list, re-tying it backwards as you go. If you reach the end, there's no loop. If the order is important, you can re-tie again, still in O(N) ti
by pps43 7y ago
Iterate over the list, re-tying it backwards as you go. If you reach the end, there's no loop. If the order is important, you can re-tie again, still in O(N) time. If you end up at the head, there's a loop.
- saagarjha 7y ago> Iterate over the list, re-tying it backwards as you go. What does "re-tying backwards" mean?
- pps43 7y agoBefore: a->b->c After: a<-b<-c
- smcl 7y agoWhat if you end up at head+1, not head?
- pps43 7y agoHow would you end up there? With a loop, head+1 would point to head after the first pass, so you'll end up at the head. With no loop, head+1 would only be passed once.
- lolc 7y agoFun and really dirty solution! I would never come up with this because I would not dare to modify a passed data structure unless this was the purpose of the procedure. One could use that answer to gauge the humour of the interviewer :-) For me the expected reaction of a peer to this would be "Cute! Now explain the problems I could encounter when using it." If they can't deal with some fun, well, their loss.
- pps43 7y agoIf you can't modify the original list, you can create another as you iterate. But that will require extra O(N) memory, so is worse than the textbook solution with two pointers.
- lolc 7y agoInteresting! I didn't know the solution with two pointers and would have assumed O(n) memory as a lower boundary. I must admit I didn't follow the bytecode too closely. So thanks for pointing that out.