Find cycle in linked list.

Question

RRR · Accepted Answer

State that you have 2 or more nodes in the list before you begin. 
Have two pointers P1 & P2. 
Have pointer P1 point to node #1 and P2 to node #2. 
Move the pointers : such that, for every node move of P1, P2 moves 2 nodes.  

(Eg): 
    P1 = P1 -> link  
    P2 = P2 -> link -> link

If at any point if P1 and P2 point to the same node, then it means that the list is in a loop.

Try this with a few connected nodes in a properly formed linked list to prove to yourself.

H. Abajyan · Answer

If the size of the list is known, the solution is to iterate through the list and keep counter until the counter reaches to the size+1 or the list ends. in first case it will mean the list has cycle, in second case, it has no cycles.
If the size is unknnown, keep a map/list of the nodes during iterating thru the list. during each iteration, check whether the node exists in the maintained map or not. If yes, the list has cycle, otherwise, add that node to the list and continue to next iteration.
Repeat this untill either list ends (no cycles) or the node is found in temporary tracked map of the nodes.

Microsoft

Domanda di colloquio di Microsoft

Risposte di colloquio

Aziende seguite

Ricerche di lavoro