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.