3 ms·

> In this case, the generally “correct” answer is a tortoise-and-hare algorithm, where you have two pointers at the head of your linked list, one traverses the

> In this case, the generally “correct” answer is a tortoise-and-hare algorithm, where you have two pointers at the head of your linked list, one traverses the list two nodes at a time, and one traverses the list one node at a time; if ever the pointers point to the same node, you have a cycle somewhere. I'm an extreme novice to programming. I don't fully understand this. 1) How can you traverse a linked list two nodes at a time? Is this just short-hand for "go to the next node, then go to the node after that, and call that one operation"? 2) If you can detect when two pointers are pointing to the same address, couldn't you solve the problem by traversing the list one node at a time, storing the addresses of each node in an array, and checking to see if the array contains any duplicate values at intervals?

nayefc 12y ago
1) One loop, two pointers. Each iteration increments each pointer by a different margin. 2) Yes you can do this but not in all languages.
mankyd 12y ago
The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If the hare hits a null node, there's no loop. If the hare hits a cycle, it will eventually run back into the tortoise and there's a loop.
- pessimizer 12y ago
  I must have learned this algorithm in school, but completely forgot it. My naive implementation was 2), but this is the first explanation on this page that made Floyd’s cycle-finding algorithm click for me:) Now I can't unknow it - thanks for the clarity and concision!
aquamongoose 12y ago
With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-and-hare algorithm uses only O(1) memory. Here's how it works: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...
- thisone 12y ago
  unless the interviewer plans to move the goal posts, there was no specified memory restriction in the original question.
  - gohrt 12y ago
    Complexity optimization is a generally useful skill. "moving the goal posts" is called "every month at work, when you finish 1 task and then move on to another task, instead of going home and getting paid to rest on your laurels"
    - thisone 12y ago
      moving goal posts, is "I asked you for x, you provided me with x, but I really wanted y, so now I'm going to tell you you're wrong" You want someone to answer a programming question within a particular set of boundaries, you set those boundaries.
      - dllthomas 12y ago
        I don't think it has to be "wrong". If I were asking this question, and I was provided with "store them in a hash", I would say something along the lines of "that's a correct solution" and then add additional constraints. "How you adapt in the face of additional constraints" is very much relevant to programming.
yodsanklai 12y ago
1) yes. 2) is ok (with a hash table instead of an array to have linear execution time), but doesn't run in constant space unlike 1), or you could mark the nodes when you visit them.
mnw21cam 12y ago
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.

nayefc 12y ago

1) One loop, two pointers. Each iteration increments each pointer by a different margin. 2) Yes you can do this but not in all languages.

mankyd 12y ago

The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If the hare hits a null node, there's no loop. If the hare hits a cycle, it will eventually run back into the tortoise and there's a loop.

pessimizer 12y ago
I must have learned this algorithm in school, but completely forgot it. My naive implementation was 2), but this is the first explanation on this page that made Floyd’s cycle-finding algorithm click for me:) Now I can't unknow it - thanks for the clarity and concision!

aquamongoose 12y ago

With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-and-hare algorithm uses only O(1) memory. Here's how it works: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...

thisone 12y ago
unless the interviewer plans to move the goal posts, there was no specified memory restriction in the original question.
- gohrt 12y ago
  Complexity optimization is a generally useful skill. "moving the goal posts" is called "every month at work, when you finish 1 task and then move on to another task, instead of going home and getting paid to rest on your laurels"
  - thisone 12y ago
    moving goal posts, is "I asked you for x, you provided me with x, but I really wanted y, so now I'm going to tell you you're wrong" You want someone to answer a programming question within a particular set of boundaries, you set those boundaries.
    - dllthomas 12y ago
      I don't think it has to be "wrong". If I were asking this question, and I was provided with "store them in a hash", I would say something along the lines of "that's a correct solution" and then add additional constraints. "How you adapt in the face of additional constraints" is very much relevant to programming.

yodsanklai 12y ago

1) yes. 2) is ok (with a hash table instead of an array to have linear execution time), but doesn't run in constant space unlike 1), or you could mark the nodes when you visit them.

mnw21cam 12y ago

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.