How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Detect and Break a Cycle in a Singly Linked List

Quick Overview

This question tests practical knowledge of linked list traversal and pointer manipulation, specifically the ability to detect and resolve cycles using space-efficient algorithms. It evaluates algorithmic reasoning and low-level data structure skills commonly assessed in software engineering interviews.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the `head` of a singly linked list. The list **may or may not contain a cycle**: somewhere in the list, one node's `next` pointer may point back to an earlier node, forming a loop. Do two things: 1. **Detect** whether the list contains a cycle. 2. If a cycle exists, **break it** by setting the `next` pointer of the *offending* node to `NULL`. The offending node is the last node *inside* the cycle — the one whose `next` currently points back to the **cycle entry** (the first node of the loop). After your function returns, the list must be a proper, acyclic, NULL-terminated singly linked list whose nodes are otherwise unchanged. Return whether a cycle was found (and, implicitly, leave the list de-cycled). ### Definitions - The **cycle entry** is the first node that is part of the loop — the node that the offending `next` points back to. - The **offending node** is the node immediately *before* the cycle entry along the loop (i.e. the loop's last node), whose `next` you must rewrite to `NULL`. ### Notes - You must not modify node values, and you must not change any `next` pointer other than the single offending one. - Aim for `O(n)` time and `O(1)` extra space. ### Constraints - `0 <= number of nodes <= 10^5`. - Node values fit in a 32-bit integer. - There is at most one cycle. ### Input / Output - **Input:** the `head` of the list (the cycle, if any, is encoded by the test harness via a 0-indexed `pos` of the cycle-entry node, where `pos = -1` means no cycle). - **Output:** a boolean — `true` if a cycle was detected and broken, `false` if the list was already acyclic. After the call, the list is acyclic. ### Examples **Example 1** ``` List: 3 -> 2 -> 0 -> -4, with the last node (-4) pointing back to node at index 1 (value 2). Output: true After: 3 -> 2 -> 0 -> -4 -> NULL (the -4 node's next is now NULL) ``` **Example 2** ``` List: 1 -> 2, with node at index 1 (value 2) pointing back to index 0 (value 1). Output: true After: 1 -> 2 -> NULL ``` **Example 3** ``` List: 1 -> 2 -> 3 -> NULL (no cycle) Output: false After: 1 -> 2 -> 3 -> NULL (unchanged) ```

Quick Answer: This question tests practical knowledge of linked list traversal and pointer manipulation, specifically the ability to detect and resolve cycles using space-efficient algorithms. It evaluates algorithmic reasoning and low-level data structure skills commonly assessed in software engineering interviews.

You are given the `head` of a singly linked list. The list **may or may not contain a cycle**: somewhere in the list, one node's `next` pointer may point back to an earlier node, forming a loop. Do two things: 1. **Detect** whether the list contains a cycle. 2. If a cycle exists, **break it** by setting the `next` pointer of the *offending* node to `NULL`. The offending node is the last node *inside* the cycle — the one whose `next` currently points back to the **cycle entry** (the first node of the loop). After your function returns, the list must be a proper, acyclic, NULL-terminated singly linked list whose nodes are otherwise unchanged. Return whether a cycle was found (and, implicitly, leave the list de-cycled). ### Definitions - The **cycle entry** is the first node that is part of the loop — the node that the offending `next` points back to. - The **offending node** is the node immediately *before* the cycle entry along the loop (i.e. the loop's last node), whose `next` you must rewrite to `NULL`. ### Harness encoding (for this console) Because the runner passes plain values, the list is encoded as two arguments: - `values`: the node values in order, e.g. `[3, 2, 0, -4]`. - `pos`: the 0-indexed position of the **cycle entry** that the last node's `next` points back to; `pos = -1` means **no cycle**. Your function must build the list (introducing the cycle when `pos != -1`), detect and break any cycle, and return `[found, values_after]` where `found` is the boolean and `values_after` is the list's values after the (possible) break — which must always be acyclic and equal to the original `values`. ### Notes - You must not modify node values, and you must not change any `next` pointer other than the single offending one. - Aim for `O(n)` time and `O(1)` extra space. ### Constraints - `0 <= number of nodes <= 10^5`. - Node values fit in a 32-bit integer. - There is at most one cycle. ### Examples **Example 1** ``` values = [3, 2, 0, -4], pos = 1 -> [true, [3, 2, 0, -4]] (-4's next, which pointed back to value 2, is now NULL) ``` **Example 2** ``` values = [1, 2], pos = 0 -> [true, [1, 2]] ``` **Example 3** ``` values = [1, 2, 3], pos = -1 -> [false, [1, 2, 3]] ```

Constraints

0 <= number of nodes <= 10^5
Node values fit in a 32-bit integer
There is at most one cycle
pos is in [-1, number of nodes - 1]; pos = -1 means no cycle

Examples

Input: ([3, 2, 0, -4], 1)

Expected Output: [True, [3, 2, 0, -4]]

Explanation: -4 (index 3) points back to value 2 (index 1). Floyd detects the cycle; the entry is value 2; the offending node is -4, whose next is reset to NULL. List stays [3,2,0,-4] but is now acyclic.

Input: ([1, 2], 0)

Expected Output: [True, [1, 2]]

Explanation: Node 2 points back to node 1 (the head). Entry is the head; the offending node is 2; its next becomes NULL.

Input: ([1, 2, 3], -1)

Expected Output: [False, [1, 2, 3]]

Explanation: No cycle: fast pointer reaches NULL, so found is false and the list is returned unchanged.

Input: ([], -1)

Expected Output: [False, []]

Explanation: Empty list edge case — head is NULL, the loop never runs, no cycle.

Input: ([7], 0)

Expected Output: [True, [7]]

Explanation: Single node self-loop (its next points to itself). Floyd still detects it via fast.next; the entry and offending node are the same node, whose next is reset to NULL.

Input: ([7], -1)

Expected Output: [False, [7]]

Explanation: Single node, no cycle — found is false, list unchanged.

Input: ([5, 5, 5, 5, 5], 2)

Expected Output: [True, [5, 5, 5, 5, 5]]

Explanation: Duplicate values must not confuse detection — identity (node references), not value equality, drives the algorithm. The cycle from the tail back to index 2 is detected and broken.

Input: ([-1, -2, -3, -4, -5, -6], 0)

Expected Output: [True, [-1, -2, -3, -4, -5, -6]]

Explanation: Negative values and a full-list cycle (tail back to head). Entry is the head; offending node is the last node.

Input: ([10, 20, 30, 40, 50], 4)

Expected Output: [True, [10, 20, 30, 40, 50]]

Explanation: Self-loop on the last node only (tail points to itself, pos=4). A minimal one-node cycle at the tail; it is detected and broken without touching earlier nodes.

Hints

Use Floyd's tortoise-and-hare: a slow pointer (1 step) and a fast pointer (2 steps). If they ever meet, there is a cycle; if fast reaches NULL, there is not.
After the meeting point is found, reset one pointer to head and advance both one step at a time. They meet again exactly at the cycle entry — this is the classic distance-equality argument (head-to-entry distance equals meeting-point-to-entry distance around the loop).
The offending node is the node *just before* the entry along the loop — i.e. walk from the entry around the cycle until you find the node whose `next` is the entry, then set that `next` to NULL. Do not touch any other pointer or any value.

Quick Overview