How to detect loops in a linked list without using a data structure

Question

jeremy · Accepted Answer

start a fast pointer and a slow pointer each traversing the list. if they ever point to the same place after the start, then they are both caught in the same loop.

Straightforward · Answer

Check out the Wiley's book "programming interviews exposed" that discusses this question in detail. Coming up with jeremy's solution on the spot is close to impossible.
You could check for every position i you come by as you jump from node to node, if any of the previous i-2 nodes' next pointer points to you. If there is a cycle, one will point to you.

kshitij · Answer

fastest way: 
suppose there is 'value' field in each node of linked list other that ther 'next node pointer'

as you traverse the list .. make the value field -1 or something like MAX_INT.... keep doing it either list ends or you see MAX_INT again...

dopey · Answer

Jeremy's answer is right; it's called Floyd's cycle finding algorithm

Amazon

Question d’entretien chez Amazon

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois