Re:The Worst Programming Interview Question
by mnw21cam on Friday June 27, 2014 @10:34AM
(#7954073)
1) Yes, that's exactly it. node := node.next.next
2) Yes, you could, and that is a valid way to discover a loop. However, consider that your linked list is already a store of the contents of the list. Rather than copying values out, you may as well use the list itself.
If you could assume that the loop contains all members of the list, then you could detect the loop by iterating through the list and checking to see if the node is the same as the head of the list. Unfortunately, the loop doesn't always point back to the head of the list, so you may have something like this:
1 -> 2 -> 3
| |
^ \/
5 <- 4
By maintaining two node references, and advancing one of them twice as quickly as the other, you are effectively doing the exact same check, but eliminating the problem that the loop may not include the head. In both tests, the separation between the two referenced nodes increases by one every time, but only in the second test is the "head" reference guaranteed to eventually be in the loop.
2) Yes, you could, and that is a valid way to discover a loop. However, consider that your linked list is already a store of the contents of the list. Rather than copying values out, you may as well use the list itself.
If you could assume that the loop contains all members of the list, then you could detect the loop by iterating through the list and checking to see if the node is the same as the head of the list. Unfortunately, the loop doesn't always point back to the head of the list, so you may have something like this:
By maintaining two node references, and advancing one of them twice as quickly as the other, you are effectively doing the exact same check, but eliminating the problem that the loop may not include the head. In both tests, the separation between the two referenced nodes increases by one every time, but only in the second test is the "head" reference guaranteed to eventually be in the loop.