Coding interview: Detect if a linked list has loop

To interviewers: Please do not use this question to interview other people. Because it is basically useless. You probably won’t get much information out of it. If the candidate answered it properly, it is most likely they have seen this question before. And if you have not seen this before, read on.

First, let’s define the linked list node:

You do not need to do the getter and setter but it just shows that you have good coding behavior.

Wrong approaches to the question include but not limited to:
1. Have one pointer keep moving to the next node and see if comes back to the header. The loop does not have to make a complete circle. For example: 1->2->3->4->5->2
2. Go through the list and save node in a hash map (or other type of storage) to see if we get a node that we have already seen before. This mostly works but won’t on huge linked list. You are guaranteed to ran out of memory.

Correct solution: Have 2 pointers, one go through the list at speed 1 node per loop and one go through the list at speed 2 nodes per loop.

Now, have while (true) in production code is not a good idea, but OK here for it simplifies the logic and make code easier to understand.

One small twist you can add to the question is: Fix the loop in the linked list. This boils down to a simple math problem. The solution is after the 2 pointers meet, move one of them back to the head, start to move the again but this time 1 node per loop for both of them. They will meet again and where they meet is the node that the linked list is looped back to so you can break there.

Again, do NOT use this question to interview other people. It really does not tell you much about the candidate.