Last reviewed
Correct answer: D. Detecting cycles or finding a middle element
Explanation
Walk two pointers from the head, one moving a single step per iteration and the other moving two. If the list ends, the fast pointer reaches null first and you know the chain is finite. If instead the tail links back into the list, the fast pointer is stuck inside that loop and closes the gap on the slow pointer by one node per iteration, so a collision is guaranteed. NIST defines a circular list as a variant of a linked list in which the nominal tail is linked to the head, which is exactly the condition this walk exposes.
The same two-speed walk hands you the middle for free: when the fast pointer falls off the end, the slow pointer sits at the halfway node. Both jobs finish in one pass with constant extra memory and no prior knowledge of the length, which is why interviewers reach for it.
Nothing about the technique deletes nodes, and it neither copies the list into an array nor sorts anything. Those answers describe unrelated operations that would each cost O(n) extra space or an ordering pass.
Sources
“A variant of a linked list in which the nominal tail is linked to the head. The entire list may be accessed starting at any item and following links until one comes to the starting item again.”
“A path that starts and ends at the same vertex and includes at least one edge.”
“An ordinary linked list must be searched with a linear search.”
Practise 3 questions on this topic
Take Linked Lists — Timed Test (3 questions) — scored instantly, explanation for every question, no login.