Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Amazon SWE interview with a linked list problem that sounds straightforward until you actually read the full requirements. The cycle detection part is fine, the 'now break it cleanly' part is where things get interesting.

Questions Asked (1)

Given the head of a singly linked list that may contain a cycle, detect whether a cycle exists and, if so, remove it by setting the offending node's next pointer to NULL. The offending node is the last node in the loop, the one whose next currently points back to the cycle entry. Return true if a cycle was found and broken, false otherwise. Do this in O(n) time and O(1) space.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Floyd's algorithm gets you to cycle detection pretty fast, most people know that part.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use Floyd's cycle detection algorithm (tortoise and hare) to determine if a cycle exists and find the meeting point. Then, reset one pointer to the head and move both pointers one step at a time until they meet at the cycle entry. Finally, traverse to the last node of the cycle and set its next pointer to NULL.

Pro tip: After finding the cycle entry, to remove the cycle, you can either traverse from the entry to find the node whose next is the entry, or use a more efficient method: while finding the entry, keep track of the previous node. This shows you understand optimization even within O(n).

1. Detect cycle with Floyd's algorithm

Initialize two pointers, slow and fast, at the head. Move slow one step and fast two steps at a time until they meet or fast reaches the end. If fast reaches the end, no cycle exists, return false.

2. Find cycle entry point

If a cycle is detected, reset one pointer to the head and keep the other at the meeting point. Move both one step at a time until they meet; the meeting node is the start of the cycle.

3. Locate last node of cycle

Starting from the cycle entry, traverse the cycle until you reach the node whose next pointer points back to the entry. That node is the last node of the cycle.

4. Remove cycle and return true

Set the next pointer of the last node to NULL to break the cycle. Return true to indicate the cycle was found and removed.

Key Points to Mention

Floyd's cycle detection algorithm (tortoise and hare) for O(n) time and O(1) space.
Mathematical proof that the meeting point and head are equidistant from the cycle entry.
Edge cases: empty list, single node, cycle at head, no cycle.
Time complexity: O(n) for detection and O(n) for finding entry and removing, overall O(n).
Space complexity: O(1) as only pointers are used.
Alternative approaches like hashing would use O(n) space, so Floyd's is optimal.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.