starting node of a loop in linked list

PHOTO EMBED

Fri Jul 19 2024 12:18:25 GMT+0000 (Coordinated Universal Time)

Saved by @vishnu_jha ##c++ ##dsa ##linkedlist ##circular ##loop #floyd'sloopdetection ##algorithm

node *floyedDetectionLoop(node *head) {
  if (head == NULL) {
    return NULL;
  }
  node *fast = head;
  node *slow = head;
  while (fast != NULL && slow != NULL) {
    fast = fast->next;
    if (fast->next != NULL) {
      fast = fast->next;
    }
    slow = slow->next;
    if (fast == slow) {
      return slow;
    }
  }
  return NULL;
}

node *getStartingNode(node *head) {
  if (head == NULL) {
    return NULL;
  }
  node *intersection = floyedDetectionLoop(head);
  node *slow = head;
  while (slow != intersection) {
    slow = slow->next;
    intersection = intersection->next;
  }
  return slow;
}
content_copyCOPY