removeCycle<T> function

LinkedListNode<T>? removeCycle<T>(LinkedListNode<T>? head)

Removes the cycle from the linked list if it exists

head - The head of the linked list Returns the head of the linked list with cycle removed

Time Complexity: O(n) where n is the length of the list Space Complexity: O(1)

Implementation

LinkedListNode<T>? removeCycle<T>(LinkedListNode<T>? head) {
  if (head == null || head.next == null) return head;

  LinkedListNode<T>? slow = head;
  LinkedListNode<T>? fast = head;

  // First phase: find the meeting point
  bool hasCycle = false;
  while (fast != null && fast.next != null) {
    slow = slow!.next;
    fast = fast.next!.next;

    if (slow == fast) {
      hasCycle = true;
      break;
    }
  }

  // If no cycle, return original head
  if (!hasCycle) return head;

  // Second phase: find the start of the cycle
  slow = head;
  while (slow!.next != fast!.next) {
    slow = slow.next;
    fast = fast.next;
  }

  // Remove the cycle
  fast.next = null;

  return head;
}