Detect loop in a linked list

June 23, 2022 · 1 min read

https://practice.geeksforgeeks.org/problems/detect-loop-in-linked-list/1

Floyd’s tortoise and hare algorithm

class Solution {
public:
  bool detectLoop(Node *head) {
    Node *hare = head, *tortoise = head;

    if (head == nullptr || head->next == nullptr)
      return false;

    while (hare != nullptr && tortoise != nullptr) {
      tortoise = tortoise->next;
      hare = hare->next;
      hare = hare ? hare->next : hare;
      if (hare == tortoise) {
        return true;
      }
    }

    return false;
  }
};
Reverse a linked list in group of given size
Delete loop in a linked list