Detect and Remove Cycles in Linked Lists

General
1

How can you detect and remove a cycle in a linked list efficiently? Explain the approach, algorithm, and time and space complexity, preferably with an example.

2

The most efficient way to detect and remove a cycle in a linked list is Floyd’s Cycle Detection Algorithm, also called the Tortoise and Hare Algorithm. It uses two pointers moving at different speeds, allowing cycle detection in O(n) time with O(1) extra space.

1. Detect the Cycle Using Slow and Fast Pointers

Use two pointers:

  • Slow pointer: Moves one node at a time.
  • Fast pointer: Moves two nodes at a time.
  • If the linked list has no cycle, the fast pointer eventually reaches None.
  • If a cycle exists, the slow and fast pointers eventually meet inside the loop.

2. Find the Starting Node of the Cycle

After both pointers meet:

  • Move the slow pointer back to the head.
  • Keep the fast pointer at the meeting point.
  • Move both pointers one node at a time.
  • The node where they meet again is the starting point of the cycle.

3. Remove the Cycle

Once the cycle starting node is known:

  • Traverse the cycle until finding the node whose next points to the cycle start.
  • Set that node’s next to None.
  • The linked list becomes linear again.

Example

Consider this linked list:

1 → 2 → 3 → 4 → 5
↑ ↓
← ← ← ←

Here, node 5 points back to node 2, creating a cycle.

Floyd’s algorithm detects the cycle when the slow and fast pointers meet. After identifying node 2 as the cycle start, traverse until node 5 and set:

5.next = None

The resulting linked list becomes:

1 → 2 → 3 → 4 → 5 → None

Python Implementation

def detect_and_remove_cycle(head):

slow = fast = head

\# Detect cycle

while fast and fast.next:

    slow = slow.next

    fast = fast.next.next

    if slow == fast:

        break

else:

    return head

\# Find cycle starting point

slow = head

if slow == fast:

    while fast.next != slow:

        fast = fast.next

else:

    while slow.next != fast.next:

        slow = slow.next

        fast = fast.next

\# Remove cycle

fast.next = None

return head

Time and Space Complexity

  • Time Complexity: O(n) because each pointer traverses the linked list a limited number of times.
  • Space Complexity: O(1) because no additional data structure is required.

Using Floyd’s Cycle Detection Algorithm is generally preferred for linked list cycle detection because it detects and removes loops efficiently without requiring extra memory.