JavaScript: Detect a Cycle in a Linked List

1. Introduction

A common problem with linked lists is the potential for a cycle, where a node references an earlier node in the sequence, creating an infinite loop. Detecting such a cycle is essential for preventing infinite loops in operations that traverse the linked list. In this guide, we will walk through the implementation of an algorithm, known as Floyd's cycle-finding algorithm, or the "Tortoise and the Hare" technique, to detect a cycle in a linked list.

2. Program Overview

1. Define the Node class for linked list nodes.

2. Define the LinkedList class with methods: add and hasCycle.

3. Use the "Tortoise and the Hare" technique to detect a cycle.

3. Code Program

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

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

    // Function to add a node to the end of the linked list
    add(value) {
        let newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Function to check for a cycle in the linked list
    hasCycle() {
        if (!this.head || !this.head.next) {
            return false;
        }
        let slow = this.head; // the tortoise
        let fast = this.head.next; // the hare

        while (fast && fast.next) {
            if (fast === slow) {
                return true; // cycle detected
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}

// Example

const list = new LinkedList();
list.add("A");
list.add("B");
list.add("C");
list.add("D");

// Intentionally create a cycle for demonstration
list.head.next.next.next.next = list.head.next;

console.log(list.hasCycle()); // Outputs: true

4. Step By Step Explanation

1. Node Class: This represents individual elements in our linked list. Each node contains a value and a reference to the next node.

2. LinkedList Class:

- Starts with an initial head node set to null.- The add method allows you to add a new node to the end of the linked list.

- The hasCycle method checks if there's a cycle using two pointers: a slow-moving one (tortoise) and a fast-moving one (hare). If there's a cycle, the hare will eventually meet the tortoise.

3. Example: We first construct a linked list with 4 nodes. Then, we deliberately create a cycle by pointing the last node back to the second node. Our hasCycle function correctly identifies the presence of this cycle.

The "Tortoise and the Hare" technique is an efficient way to detect a cycle in a linked list, running in O(n) time and using O(1) space.