AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Easylinked listcycle

~60s

Detecting a loop in constant space

Which technique detects a loop in a singly linked list using only O(1) extra space?

Show the answer and the worked solution

Correct answer: A.

Floyd's cycle-finding algorithm with a slow and a fast pointer

Worked solution

  1. A hash set of visited nodes does detect a loop, but it grows to O(n) space.
  2. Sorting addresses needs the addresses collected first, which is also O(n) space, and Kadane's algorithm solves a maximum-subarray problem entirely unrelated to lists.
  3. Floyd's cycle-finding algorithm with a slow and a fast pointer advances one pointer one node at a time and the other two at a time; inside a loop the fast pointer gains one node per step until the two meet, and only two pointers are ever stored.

Answer: Floyd's cycle-finding algorithm with a slow and a fast pointer.

The idea

The tortoise-and-hare test is the standard O(1)-space loop detector, and the meeting point also lets you find where the loop starts and how long it is.

Shortcut. O(1) space rules out anything that stores nodes, the hash set and the sorted addresses, and Kadane's algorithm solves maximum subarray, which leaves the two-pointer method.

Common trap. "Recording every visited node in a hash set" does detect a loop and is the usual first idea, but it needs O(n) space.

Data Structures & Algorithms

11 of 40

Level

Easy

Target time

~60s

PreviousNext
AI InterviewGet started

Detecting a loop in constant space — Aptitude Question

Detecting a loop in constant space: Which technique detects a loop in a singly linked list using only O(1) extra… Answer and worked solution on CodeKairo.

Question

Which technique detects a loop in a singly linked list using only O(1) extra space?

Options

  1. Floyd's cycle-finding algorithm with a slow and a fast pointer
  2. Kadane's algorithm
  3. Recording every visited node in a hash set
  4. Sorting the node addresses and looking for a repeat
Show the answer and the worked solution

Correct answer: A. Floyd's cycle-finding algorithm with a slow and a fast pointer

Worked solution

  1. A hash set of visited nodes does detect a loop, but it grows to O(n) space.
  2. Sorting addresses needs the addresses collected first, which is also O(n) space, and Kadane's algorithm solves a maximum-subarray problem entirely unrelated to lists.
  3. Floyd's cycle-finding algorithm with a slow and a fast pointer advances one pointer one node at a time and the other two at a time; inside a loop the fast pointer gains one node per step until the two meet, and only two pointers are ever stored.

Answer: Floyd's cycle-finding algorithm with a slow and a fast pointer.

The idea

The tortoise-and-hare test is the standard O(1)-space loop detector, and the meeting point also lets you find where the loop starts and how long it is.

Shortcut. O(1) space rules out anything that stores nodes, the hash set and the sorted addresses, and Kadane's algorithm solves maximum subarray, which leaves the two-pointer method.

Common trap. "Recording every visited node in a hash set" does detect a loop and is the usual first idea, but it needs O(n) space.

All Data Structures & Algorithms questions · placement mock tests