16.01.2024 в 01:03

Обнаружение и удаление цикла в связанном списке

Знали ли вы о циклах в связанном списке? Что происходит, когда цикл проникает в него? В этой статье мы рассмотрим эти вопросы и углубимся в циклы в связанных списках, понимая необходимость их удаления, методы обнаружения и способы их исправления.

Введение в ListNode

ListNode — это простая структура данных, представляющая один элемент списка. В основном он состоит из двух компонентов: Value (фактическая информация или данные, которые содержит узел) и Next Pointer (указывает на следующий узел в последовательности, образуя связь между узлами в связанном списке).

Что такое цикл в связанном списке?

В связанном списке “cycle” возникает, когда узлы образуют петлю, а не прямую линию. Это похоже на узел, который указывает на предыдущий, создавая круг. Представьте, что у вас есть узлы A, B, C и D в связанном списке. Если узел A указывает на B, B указывает на C, C указывает на D, а D указывает обратно на C, вы создали цикл.

В чем необходимость его удаления?

Вы не хотите разбить свой самолет. Точно так же циклы в связанном списке подобны циклам, которые могут превратить вашу программу в бесконечную игру! Они продолжают повторяться и в конечном итоге выходят из строя, поэтому их поиск и исправление важны для бесперебойной работы.

Теперь, когда мы знаем о ListNode, ListNode Cycles и их проблеме, давайте рассмотрим реальный пример и посмотрим, как мы решаем эту проблему.

Пример обнаружения и удаления циклов в связанном списке

Слышали ли вы когда-нибудь о трюке со счетом овец? Всякий раз, когда кто-то изо всех сил пытается заснуть, он использует эту технику, чтобы погрузиться в сладкие сны. Если вы с ним знакомы, давайте превратим его в программу!

Мы создадим сценарий JavaScript, в котором будем считать 1 овцу, 2 овцы, 3 овцы и так далее, пока пользователь не задремал, используя связанный список. Однако мы намеренно введем цикл, чтобы показать вам, как он может нарушить ход нашей программы.

Код

// 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);

В приведенном выше коде:

Класс Sheep создается для представления каждой овцы в связанном списке. У каждой овцы есть свойство name и свойство next, указывающее на следующую овцу в последовательности.

Функция createSheepList генерирует связанный список овец от «1» до «5». Он намеренно вводит цикл между овцами «4» и «5», чтобы создать цикл в списке и вернуть начало списка.

Функция displayList печатает имена овец в связанном списке. Он обрабатывает циклы, чтобы избежать бесконечных циклов, устанавливая ограничение на повторения. Понятно, что вам не хотелось бы бесконечного повторения 4-5-4-5 на экране терминала. В этом примере мы установили максимальное количество итераций равным 10, чтобы предотвратить бесконечное отображение консоли.

Основная программа создает связанный список овец с помощью createSheepList. Затем он отображает количество овец с помощью displayList и печатает имена овец до тех пор, пока не будет достигнуто максимальное количество итераций, предотвращая бесконечный цикл.

Выход:

Иллюстрация:

В этой программе мы уже знаем, где находится цикл. Однако в тех случаях, когда мы этого не делаем, мы можем использовать методы обнаружения, такие как алгоритм Флойда, и исправить это. Давайте рассмотрим, что представляет собой алгоритм Флойда, и попробуем использовать его в приведенном выше коде.

Использование алгоритма Флойда

Алгоритм обнаружения циклов Флойда, также известный как алгоритм черепахи и зайца, обеспечивает эффективный способ обнаружения циклов в связанных списках.

Прежде чем мы перейдем к коду, давайте сначала поймем алгоритм:

Овцы в замешательстве, поэтому зовут на помощь своих друзей-животных: зайца и черепаху. Оба начинают с первой овцы в ряду из 5 овец (с номерами от 1 до 5). Заяц делает два шага за раз, а черепаха делает один шаг за раз. Из-за цикла между 4-й и 5-й овцой заяц и черепаха в конечном итоге встречаются внутри петли. Точка их встречи показывает цикл.

Теперь давайте реализуем приведенную выше логику в нашем коде.

Код

// 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);

В обновленном коде:

Мы инициализируем два указателя, медленный и быстрый, начиная с начала списка. Медленный указатель перемещается на один шаг за раз, а быстрый указатель перемещается на два шага за раз. Если есть цикл, два указателя встретятся.

Когда точка встречи обнаружена, функция DetectAndRemoveCycle вызывает функцию removeCycle, чтобы исправить цикл.

Сброс одного указателя на начало связанного списка. Перемещайте оба указателя шаг за шагом, пока они снова не встретятся. Установите для следующей точки встречи значение null. Это действие удаляет цикл в связанном списке.

Выход:

Заключение

Это все, что касается этой статьи. Помните, что циклы могут проникнуть в ваши связанные списки! Следите за этими циклами и используйте методы обнаружения, такие как алгоритм Флойда, чтобы найти и исправить их.

Если вас это впечатлило, обязательно посмотрите: