Question d'entretien d'embauche Microsoft: Find cycle in linked list.... |

Question d'entretien d'embauche

Entretien de Software Development Engineer In Test (SDET) II Redmond, WA (États-Unis)

Find cycle in linked list.


Réponse de l'entretien

2 réponses


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.

H. Abajyan, le 2011-04-02

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.

    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.

RRR, le 2012-08-16

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire