Detect loop in linked list using Floyd’s algorithm

Detecting a loop in a linked list is a common problem in computer science, and one way to solve it is by using Floyd’s algorithm, also known as the “tortoise and hare” algorithm. Floyd’s algorithm uses two pointers to traverse the linked list and detect if there is a loop in it.

Here’s how you can implement Floyd’s algorithm to detect a loop in a linked list:

function detectLoop(head):
    // Initialize two pointers
    slow = head
    fast = head

    // Traverse the linked list using two pointers
    while fast != null and fast.next != null:
        // Move slow pointer one step
        slow = slow.next
        // Move fast pointer two steps
        fast = fast.next.next

        // Check if slow and fast pointers meet
        if slow == fast:
            return true

    // If the fast pointer reaches the end of the list, there is no loop
    return false

In this pseudocode, head is the head of the linked list. We initialize two pointers called slow and fast to the head of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.

If there is no loop in the linked list, the fast pointer will reach the end of the linked list before the slow pointer, and we can return false to indicate that there is no loop.

If there is a loop in the linked list, the fast pointer will eventually catch up to the slow pointer, meaning that they will both point to the same node in the loop. In this case, we can return true to indicate that there is a loop.

Note that Floyd’s algorithm has a time complexity of O(n), where n is the length of the linked list, and a space complexity of O(1), meaning it does not require any additional space to detect a loop in the linked list.

Code in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def detect_loop(head):
    # initialize two pointers
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        # move slow pointer one step
        slow = slow.next
        # move fast pointer two steps
        fast = fast.next.next

        # check if slow and fast pointers meet
        if slow == fast:
            return True

    return False

Code in Ruby:

class Node
  attr_accessor :data, :next

  def initialize(data)
    @data = data
    @next = nil
  end
end

def detect_loop(head)
  slow = head
  fast = head

  while fast && fast.next
    slow = slow.next
    fast = fast.next.next

    if slow == fast
      return true
    end
  end

  return false
end

Code in Java:

class Node {
  int data;
  Node next;

  Node(int data) {
    this.data = data;
    this.next = null;
  }
}

public boolean detectLoop(Node head) {
  Node slow = head;
  Node fast = head;

  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow == fast) {
      return true;
    }
  }

  return false;
}

Code in JavaScript:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function detectLoop(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

In all of these implementations, we first define a Node class to represent each node in the linked list. Then, we define a function called detect_loop or detectLoop that takes the head of the linked list as a parameter.

The function initializes two pointers called slow and fast to the head of the linked list, and then uses a while loop to traverse the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.

If there is no loop in the linked list, the fast pointer will reach the end of the linked list before the slow pointer, and we can return false to indicate that there is no loop.

If there is a loop in the linked list, the fast pointer will eventually catch up to the slow pointer, meaning that they will both point to the same node in the loop. In this case, we can return true to indicate that there is a loop.

Note that Floyd’s algorithm has a time complexity of O(n), where n is the length of the linked list, and a space complexity of O(1), meaning it does not require any additional space to detect a loop in the linked list.