## Introduction

A cycle in a linked list occurs when a node's `next` pointer points back to a previous node, forming a loop. Detecting a cycle in a linked list is an important problem, as it can cause infinite loops during traversal.

One of the most efficient ways to detect a cycle is by using Floyd’s Cycle Detection Algorithm (also known as the "Tortoise and Hare" algorithm). This algorithm uses two pointers that move at different speeds: one moves one step at a time (tortoise), and the other moves two steps at a time (hare). If there is a cycle, the fast pointer will eventually meet the slow pointer.

## Problem Statement

Create a JavaScript program that:

• Detects if a given singly linked list contains a cycle using Floyd’s Cycle Detection Algorithm.

### Example:

• Input: A linked list with a cycle:

``````1 -> 2 -> 3 -> 4 -> 5
^              |
|______________|
``````
• Output: `Cycle detected in the linked list.`

• Input: A linked list without a cycle:

``````1 -> 2 -> 3 -> 4 -> 5 -> null
``````
• Output: `No cycle detected in the linked list.`

## Solution Steps

1. Define the Node Class: Create a `Node` class to represent each node in the linked list.
2. Define the Linked List Class: Create a linked list with methods to:
• Insert nodes.
• Detect if there is a cycle using Floyd's Cycle Detection Algorithm.
3. Display the Result: Output whether the linked list has a cycle.

## JavaScript Program

### Step 1: Define the Node Class

``````// JavaScript Program to Detect a Cycle in a Linked List

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

### Step 2: Define the Linked List Class

``````class LinkedList {
constructor() {
}

// Insert a node at the end of the linked list
insert(value) {
const newNode = new Node(value);

} else {
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
}

// Detect cycle using Floyd's Cycle Detection Algorithm
detectCycle() {

while (fastPointer !== null && fastPointer.next !== null) {
slowPointer = slowPointer.next;       // Move one step
fastPointer = fastPointer.next.next;  // Move two steps

if (slowPointer === fastPointer) {
console.log("Cycle detected in the linked list.");
return true;
}
}

console.log("No cycle detected in the linked list.");
return false;
}

// Helper function to create a cycle for testing
createCycle(pos) {
if (pos === -1) return;

let cycleNode = null;
let index = 0;
let lastNode = null;

while (current !== null) {
if (index === pos) {
cycleNode = current;
}
lastNode = current;
current = current.next;
index++;
}

if (lastNode !== null) {
lastNode.next = cycleNode;
}
}
}
``````

### Step 3: Example Usage

``````// Example usage of LinkedList to detect a cycle

list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);

// Create a cycle at position 1 (2nd node)
list.createCycle(1);

console.log("Checking for cycle in the linked list:");
list.detectCycle();  // Output: Cycle detected in the linked list.

// Example usage without a cycle

listWithoutCycle.insert(10);
listWithoutCycle.insert(20);
listWithoutCycle.insert(30);
listWithoutCycle.insert(40);
listWithoutCycle.insert(50);

console.log("Checking for cycle in the linked list:");
listWithoutCycle.detectCycle();  // Output: No cycle detected in the linked list.
``````

### Output Example

``````Checking for cycle in the linked list:
Cycle detected in the linked list.

Checking for cycle in the linked list:
No cycle detected in the linked list.
``````

## Explanation

### Step 1: Define the Node Class

• The `Node` class represents each node in the linked list. Each node has:
• `value`: The value stored in the node.
• `next`: A reference to the next node in the list (initialized to `null`).

### Step 2: Define the Linked List Class

• Insert: The `insert()` method adds a new node at the end of the list.
• detectCycle: This method uses Floyd’s Cycle Detection Algorithm:
• Two pointers, `slowPointer` (moves one step) and `fastPointer` (moves two steps), traverse the list.
• If the two pointers meet, a cycle is detected.
• If the `fastPointer` reaches the end of the list (`null`), no cycle is detected.
• createCycle: This helper method creates a cycle for testing purposes by connecting the last node to a node at position `pos` in the list.

### Step 3: Example Usage

• The program creates two linked lists: one with a cycle and one without.
• It uses the `detectCycle()` method to check for the presence of a cycle and prints the result.

## Time and Space Complexity

• Time Complexity: O(n), where `n` is the number of nodes in the linked list.
• Both pointers will traverse the list at most `n` steps in the worst case.
• Space Complexity: O(1), since no additional data structures are used (besides the pointers).

## Conclusion

This JavaScript program demonstrates how to detect a cycle in a linked list using Floyd’s Cycle Detection Algorithm (Tortoise and Hare). The program efficiently checks for cycles in linear time with constant space, making it an ideal solution for this problem.