Solution: Linked List Cycle IV

Statement

Given the head of a singly linked list, implement a function to detect and remove any cycle present in the list. A cycle occurs when a node's next pointer links back to a previous node, forming a loop within the list.

The function must modify the linked list in place, ensuring it remains acyclic while preserving the original node order. If no cycle is found, return the linked list as is.

Constraints:

• The number of nodes in the list is in the range $[0, 10^4]$.

• $-10^5 \leq$ Node.value $\leq10^5$

Solution

The Floyd’s Cycle Detection method is used to identify and eliminate cycles efficiently. It begins by initializing two pointers at the head of the linked list. The slow pointer moves one step, and the fast moves two steps to traverse the list. If the two pointers meet, a cycle is detected; otherwise, if fast reaches NULL, the list is cycle-free. To determine the cycle’s starting node, slow is reset to the head, and both pointers move one step at a time until they meet again. Once the cycle’s entry point is found, the algorithm traverses the loop to identify the last node in the cycle, which is the node whose next pointer refers back to the cycle start. Finally, the cycle is removed by setting this last node next to NULL, restoring the linked list to a proper linear structure.

The steps of the algorithm are as follows:

1. Initialize two pointers, slow and fast, to the head node.

2. Traverse the linked list using slow and fast pointers to detect a cycle:

   1. Move slow, one step forward.

   2. Move fast, two steps forward.

   3. If slow == fast, a cycle is detected, and we break out of the loop.

3. If fast reaches NULL, the list is cycle-free and return head.

4. Once a cycle is detected, we need to determine where it begins:

   1. Reset slow to head.

   2. Move both slow and fast, one step at a time, until they meet again. The meeting point is the starting node of the cycle.

5. To break the cycle, we must locate the last node in the loop:

   1. Start from fast, which is now at the cycle’s starting node.

   2. Move forward through the cycle until fast.next == slow (this identifies the last node in the cycle).

6. Set fast.next = NULL to break the cycle and restore the linked list to a linear structure.

7. Return the head of the modified linked list.

Let’s look at the illustration below to better understand the solution.