TypeScript: Detect a Cycle in a Linked List

1. Introduction

Detecting a cycle in a linked list is a classic problem in computer science. A cycle exists in a linked list if a node's next pointer points to any node that was visited earlier in the list. The challenge is to determine if a linked list has a cycle without using extra space. In this tutorial, we will implement Floyd’s Cycle-Finding Algorithm, also known as the "Tortoise and the Hare" technique, to solve this problem in TypeScript.

2. Program Overview

We will use two pointers that move through the list at different speeds. If there is a cycle, the two-pointers will eventually meet at some point.

3. Code Program

// Define the Node class
class Node {
    value: number;
    next: Node | null = null;

    constructor(value: number) {
        this.value = value;
    }
}

// Define the LinkedList class
class LinkedList {
    head: Node | null = null;

    // Add node to the end of the list
    append(value: number) {
        const newNode = new Node(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Detect cycle in the linked list using Floyd's cycle-finding algorithm
    hasCycle(): boolean {
        if (!this.head) return false;

        let tortoise: Node | null = this.head;
        let hare: Node | null = this.head;

        while (hare && hare.next) {
            tortoise = tortoise.next;
            hare = hare.next.next;

            if (tortoise === hare) return true;
        }

        return false;
    }
}

// Test the LinkedList class
const myList = new LinkedList();
const nodeA = new Node(5);
const nodeB = new Node(10);
const nodeC = new Node(15);

myList.head = nodeA;
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeB; // introduce a cycle

console.log(`Does the list have a cycle?: ${myList.hasCycle()}`);

4. Step By Step Explanation

1. We start by defining the Node class, where each node has:

• A value that stores the data.
• A next property that points to the next node in the list or is null if there's no next node.

2. We then define the LinkedList class which contains:

• A head property that points to the first node or is null if the list is empty.

3. Inside the LinkedList class, apart from the append method, we have the hasCycle method:

• The hasCycle method initializes two pointers, tortoise and hare, both starting at the head of the list.
• The hare moves two steps at a time while the tortoise moves one step at a time.
• If there's a cycle, the hare will eventually catch up to the tortoise, proving the existence of a cycle.
• If there's no cycle, the hare will eventually reach the end of the list.

4. To test our LinkedList, we:

• Create a linked list with three nodes (with values 5, 10, and 15).
• Introduce a cycle by making the next property of the third node point to the second node.
• Call the hasCycle method to check if the linked list contains a cycle. 

With this TypeScript implementation, one can efficiently detect a cycle in a linked list without using any additional space.