Detect and Remove Cycle in Linked List

Given a linked list, detect if a cycle exists. If yes, remove the cycle and return the head of the list.

Difficulty:

JavaScript Solution

function detectAndRemoveCycle(head){
  let slow = head, fast = head;
  let hasCycle = false;
  while(fast && fast.next){
    slow = slow.next;
    fast = fast.next.next;
    if(slow === fast){ hasCycle = true; break; }
  }
  if(!hasCycle) return head;
  slow = head;
  while(slow.next !== fast.next){ slow = slow.next; fast = fast.next; }
  fast.next = null;
  return head;
}

Explanation: Detect cycle with slow/fast pointers. Move slow to head, keep fast at meeting point. Move both one step until next matches to remove cycle.

⏱ O(n) | 💾 O(1)

Java Solution

class Solution {
  public ListNode detectAndRemoveCycle(ListNode head){
    ListNode slow = head, fast = head;
    boolean hasCycle = false;
    while(fast != null && fast.next != null){
      slow = slow.next; fast = fast.next.next;
      if(slow == fast){ hasCycle = true; break; }
    }
    if(!hasCycle) return head;
    slow = head;
    while(slow.next != fast.next){ slow = slow.next; fast = fast.next; }
    fast.next = null;
    return head;
  }
}

Explanation: Floyd’s cycle detection plus removal by aligning slow and fast pointers.

⏱ O(n) | 💾 O(1)

Python Solution

def detect_and_remove_cycle(head):
    slow = fast = head
    has_cycle = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    if not has_cycle:
        return head
    slow = head
    while slow.next != fast.next:
        slow = slow.next
        fast = fast.next
    fast.next = None
    return head

Explanation: Detect cycle using two pointers, then remove cycle by aligning pointers.

⏱ O(n) | 💾 O(1)

Console

🎬 Share Your Coding Journey

Thumbnail Templates

Detect and Remove Cycle in Linked List