Detect and Remove Loop in a Linked List

Did you know about loops in a linked list? What happens when a cycle sneaks into one? In this article, we will explore these questions and delve into cycles in linked lists, understanding the need for their removal, methods for detection, and ways to fix them.

Introduction to ListNode

ListNode is a simple data structure representing a single element in the list. It mainly consists of two components: Value (the actual information or data that the node holds) and Next Pointer (points to the next node in the sequence, forming the linkage between nodes in the linked list).

What is a Cycle in a Linked List?

In a linked list, a “cycle” happens when the nodes form a loop instead of a straight line. It’s like having a node that points back to an earlier one, creating a circle. Imagine you have nodes A, B, C and D in a linked list. If node A points to B, B points to C, C points to D and D points back to C, you have created a cycle.

What is the need for its removal?

You don’t wish to crash your plane, similarly, cycles in a linked list are like loops that can turn your program into a never-ending game! It keeps on repeating and eventually crashes, that’s why finding and fixing them is important to keep things running smoothly.

Now that we know about ListNode, ListNode Cycles and its problem, let’s get into a real example and see how we fix this problem.

Example of Detecting and Removing Loops in a Linked List

Have you ever heard of the counting sheep trick? Whenever someone struggles to sleep, they use this technique to drift into sweet dreams. If you’re familiar with it, let’s turn it into a program!

We’ll create a JavaScript script where we count like 1 sheep, 2 sheep, 3 sheep, and so on until the user dozes off, using a linked list. However, we’ll intentionally introduce a cycle to show you how it can disrupt the flow of our program.

Code:

// Sheep class to represent each sheep in the linked list
class Sheep {
    constructor(name) {
      this.name = name;
      this.next = null;
    }
  }
  
  // Function to create a linked list representing counting sheep
  function createSheepList() {
    let head = new Sheep("1");
    let current = head;
  
    // Add sheep nodes for counting from 2 to 5
    for (let i = 2; i <= 5; i++) {
      current.next = new Sheep(`${i}`);
      current = current.next;
    }
  
    // Introduce intentional cycle between sheep "4" and "5"
    let cycleStart = head.next.next.next;
    current.next = cycleStart;
  
    return head;
  }
  
  
  // Function to display the linked list elements, handling cycles
function displayList(head, maxIterations = 10) {
    let current = head;
    let iterations = 0;
  
    while (current !== null && iterations < maxIterations) {
      console.log(`${current.name} sheep`);
      current = current.next;
      iterations++;
    }
  
    if (iterations === maxIterations) {
      console.log("Maximum iterations reached. Possible cycle detected.");
    }
  }
  
  
  // Main program
  const sheepList = createSheepList();
  console.log("Sheep count:");
  displayList(sheepList);

In the above code:

A Sheep class is created to represent each sheep in the linked list. Each sheep has a name property and a next property pointing to the next sheep in the sequence.
The createSheepList function generates a linked list of sheep from “1” to “5”. It intentionally introduces a cycle between the sheep “4” and “5” to create a loop in the list and the head of the list is returned.
The displayList function prints the names of the sheep in the linked list. It handles cycles to avoid endless loops by setting a limit on the repetitions. It’s clear that you wouldn’t want the endless repetition of 4-5-4-5 on your terminal screen. In this example, we’ve set the maximum iterations to 10 to prevent an endless console display.
The main program creates a linked list of sheep using createSheepList. Then, it displays the sheep count using displayList and prints the names of the sheep until the maximum iterations are reached, preventing an infinite loop.

Output:

Illustration:

In this program, we already know where the cycle is. However, in cases where we don’t, we can use detection techniques such as Floyd’s algorithm and fix it. Let’s explore what Floyd’s algorithm is and try to use it in the above code.

Using Floyd’s Algorithm

Floyd’s Cycle Detection Algorithm, also known as the tortoise and hare algorithm, provides an effective way to detect cycles in linked lists.

Before we get into the code, let’s first understand the algorithm:

The sheep are confused, so they call their animal friend: the hare and the tortoise, to help them. Both start at the first sheep in a line of 5 sheep (numbered 1 to 5). The hare moves two steps at a time, and the tortoise moves one step at a time. Because of a cycle between the 4th and 5th sheep, the hare and tortoise eventually meet inside the loop. The point where they meet shows the cycle.

Now let’s implement the above logic into our code.

Code:

// Sheep class to represent each sheep in the linked list
class Sheep {
    constructor(name) {
      this.name = name;
      this.next = null;
    }
  }
  
  // Function to create a linked list representing counting sheep
  function createSheepList() {
    let head = new Sheep("1");
    let current = head;
  
    // Add sheep nodes for counting from 2 to 5
    for (let i = 2; i <= 5; i++) {
      current.next = new Sheep(`${i}`);
      current = current.next;
    }
  
    // Introduce intentional cycle between sheep "4" and "5"
    let cycleStart = head.next.next.next;
    current.next = cycleStart;
  
    return head;
  }
  
  // Function to detect and remove a cycle in the linked list using Floyd's algorithm
  function detectAndRemoveCycle(head) {
    let slow = head;
    let fast = head;
  
    // Floyd's cycle detection algorithm
    while (fast !== null && fast.next !== null) {
      slow = slow.next;
      fast = fast.next.next;
  
      if (slow === fast) {
        // Cycle detected, remove the cycle
        removeCycle(head, slow);
        break;
      }
    }
  }
  
  // Function to remove a cycle in the linked list
  function removeCycle(head, meetPoint) {
    let ptr1 = head;
    let ptr2 = meetPoint;
  
    // Move one pointer to the start
    while (ptr1.next !== ptr2.next) {
      ptr1 = ptr1.next;
      ptr2 = ptr2.next;
    }
  
    // Set the next of the meeting point to null, removing the cycle
    ptr2.next = null;
  }
  
  // Function to display the linked list elements
  function displayList(head, maxIterations = 20) {
    let current = head;
    let iterations = 0;
  
    while (current !== null && iterations < maxIterations) {
      console.log(`${current.name} sheep`);
      current = current.next;
      iterations++;
    }
  
    if (iterations === maxIterations) {
      console.log("Maximum iterations reached. Possible cycle detected.");
    }
  }
  
  // Main program
  const sheepList = createSheepList();
  // Detect and remove the cycle
  detectAndRemoveCycle(sheepList);
  console.log("Sheep count:");
  displayList(sheepList);

In the updated code:

We initialize two pointers, slow and fast, both starting from the head of the list. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time. If there is a cycle, the two pointers will meet.
When the meeting point is detected, the detectAndRemoveCycle function calls removeCycle to fix the cycle.
Reset one pointer to the head of the linked list. Move both pointers one step at a time until they meet again. Set the next meeting point to null. This action removes the cycle in the linked list

Output:

Conclusion

That’s all for this article. Remember, loops can sneak into your linked lists! Keep an eye out for those cycles and use detection techniques like Floyd’s Algorithm to find and fix them.

If you are impressed with this one then do check out: