Remove a Loop in a Linked List
Implement removeLoop
Given the
head of a singly linked list that may contain a cycle, remove the cycle — without deleting any node — and return the head of the resulting (now normal, terminating) list.
This builds directly on Floyd's Cycle Detection: once slow and fast meet inside the cycle, the same distance property that locates the loop's first node can instead locate its last node — the one whose next pointer is the cyclic edge itself. Setting that single pointer to null is enough; no node is copied, moved, or deleted.
Example 1:
Input: head = {"vals":[3,2,0,-4],"pos":1}
Output: [3,2,0,-4]
Example 2:
Input: head = {"vals":[1,2],"pos":0}
Output: [1,2]
Example 3:
Input: head = {"vals":[1],"pos":-1}
Output: [1]
+ 5 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes in head ≤ 10⁴ - ●
-10⁹ ≤ node value ≤ 10⁹ - ●
A cyclic test list is described as (vals, pos) — the last node's next points back to index pos (0-indexed); pos = -1 means no cycle - ●
No node is deleted — only the cyclic edge is unlinked, so the returned list has the same values in the same order
head =
{"vals":[3,2,0,-4],"pos":1}