LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java MCQ · Question 19

Detecting a linked-list loop in O(1) space Answer, explanation & discussion

  • MCQ
  • Hard
  • 0 comments
  • Answer explained
  • Moderated community
Question 19 Back to Exercise

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

  • A Store visited nodes in a HashSet
  • B Floyd's slow and fast pointers Correct
  • C Sort the nodes first
  • D Reverse the list twice
Correct Answer: Option B

If there is a loop, the fast pointer (two steps) eventually laps the slow one (one step). The HashSet approach works but uses O(n) memory.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links