Detect and Remove Loop in a Linked List

Problem Given a singly linked list, detect whether it contains a cycle; if it does, remove the loop so the list becomes properly null-terminated. The list must be repaired in place.

Input / Output

• Input: head of a singly linked list (possibly cyclic).
• Output: the same list with any cycle removed.

Constraints

• Up to 10^5 nodes; O(n) time, O(1) space expected (a visited-set solution is the O(n)-space fallback).

Example

• 1→2→3→4→5→3 (5 links back to 3) → 1→2→3→4→5→null.

Expected approach

• Floyd's cycle detection: slow/fast pointers; if they meet, a cycle exists. To find the loop start, reset one pointer to head and advance both one step at a time — they meet at the cycle entry (provable via the distance equation). To remove: walk the cycle to its last node (the one whose next is the entry) and set next = null. Handle the edge case where the loop starts at the head. O(n) time, O(1) space.