findCycleStart<T> function

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

Finds the starting node of the cycle if it exists

head - The head of the linked list Returns the starting node of the cycle, or null if no cycle exists

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

Implementation

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

  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 null
  if (!hasCycle) return null;

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

  return slow;
}