🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
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.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment