JavaScript Program to Detect a Cycle in a Linked List

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
// Author: https://www.rameshfadatare.com/

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

Step 2: Define the Linked List Class

class LinkedList {
    constructor() {
        this.head = null;
    }

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

        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Detect cycle using Floyd's Cycle Detection Algorithm
    detectCycle() {
        let slowPointer = this.head;
        let fastPointer = this.head;

        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 current = this.head;
        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

const list = new LinkedList();
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

const listWithoutCycle = new LinkedList();
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.