Detect and remove a loop in a linked list.
void remove_loop(node_t *head)
{
node_t *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return; /* no loop */
slow = head;
if (slow == fast) { /* loop starts at the head */
while (fast->next != slow) fast = fast->next;
} else {
while (slow->next != fast->next) { slow = slow->next; fast = fast->next; }
}
fast->next = NULL; /* fast is the last node in the loop */
}
Points: Floyd's algorithm finds a meeting point; moving one pointer back to the head and advancing both one step at a time makes them meet at the loop's start (here we stop one node earlier so we can cut the link). Handle the case where the loop starts at the head. O(n), O(1) space.