Рубрики

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

Напишите функцию detectAndRemoveLoop (), которая проверяет, содержит ли данный Связанный список цикл, и если цикл присутствует, то удаляет цикл и возвращает true. Если список не содержит цикла, он возвращает false. На диаграмме ниже показан связанный список с циклом. detectAndRemoveLoop () должен изменить приведенный ниже список на 1-> 2-> 3-> 4-> 5-> NULL.

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

Напишите функцию C для обнаружения цикла в связанном списке

Прежде чем пытаться удалить петлю, мы должны ее обнаружить. Методы, обсужденные в вышеупомянутом посте, могут использоваться, чтобы обнаружить петлю. Чтобы удалить цикл, все, что нам нужно сделать, это получить указатель на последний узел цикла. Например, узел со значением 5 на диаграмме выше. Как только у нас есть указатель на последний узел, мы можем сделать следующий из этого узла как NULL и цикл исчезнет.
Мы можем легко использовать методы хеширования или посещения узла (обсуждаемые в вышеупомянутом посте), чтобы получить указатель на последний узел. Идея проста: самый первый узел, следующий из которых уже посещен (или хэширован), является последним узлом.
Мы также можем использовать алгоритм Floyd Cycle Detection для обнаружения и удаления петли. В алгоритме Флойда медленные и быстрые указатели встречаются в узле петли. Мы можем использовать этот узел цикла для удаления цикла. Существуют следующие два способа удаления петли, когда алгоритм Флойда используется для обнаружения петли.

Метод 1 (Проверка по одному). Мы знаем, что алгоритм обнаружения Цикла Флойда завершается, когда быстрые и медленные указатели встречаются в общей точке. Мы также знаем, что эта общая точка является одним из узлов петли (2, 3, 4 или 5 на диаграмме выше). Сохраните адрес этого в переменной указателя, скажем, ptr2. После этого начните с главы связанного списка и проверьте узлы один за другим, достижимы ли они из ptr2. Всякий раз, когда мы находим узел, который является достижимым, мы знаем, что этот узел является начальным узлом цикла в связанном списке, и мы можем получить указатель на предыдущий из этого узла.

CPP

// C ++ программа для обнаружения и удаления цикла в связанном списке
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

struct Node {

    int data;

    struct Node* next;

};

  
/ * Функция для удаления петли. Используется обнаружениемAndRemoveLoop () * /

void removeLoop(struct Node*, struct Node*);

  
/ * Эта функция обнаруживает и удаляет цикл в списке

  Если цикл был в списке, он возвращает 1,

  в противном случае возвращает 0 * /

int detectAndRemoveLoop(struct Node* list)

{

    struct Node *slow_p = list, *fast_p = list;

  

    while (slow_p && fast_p && fast_p->next) {

        slow_p = slow_p->next;

        fast_p = fast_p->next->next;

  

        / * Если slow_p и fast_p встречаются в какой-то момент, то есть

           это петля * /

        if (slow_p == fast_p) {

            removeLoop(slow_p, list);

  

            / * Вернуть 1, чтобы указать, что цикл найден * /

            return 1;

        }

    }

  

    / * Вернуть 0, чтобы выяснить, нет ли петли * /

    return 0;

}

  
/ * Функция для удаления петли.

 loop_node -> указатель на один из узлов цикла

 head -> Указатель на начальный узел связанного списка * /

void removeLoop(struct Node* loop_node, struct Node* head)

{

    struct Node* ptr1;

    struct Node* ptr2;

  

    / * Установить указатель на исправление связанного списка и

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

      часть связанного списка * /

    ptr1 = head;

    while (1) {

        / * Теперь запустите указатель из loop_node и проверьте, если он когда-либо

       достигает ptr2 * /

        ptr2 = loop_node;

        while (ptr2->next != loop_node && ptr2->next != ptr1)

            ptr2 = ptr2->next;

  

        / * Если ptr2 поменял ptr1, то есть цикл. Так сломай

        цикл * /

        if (ptr2->next == ptr1)

            break;

  

        / * Если ptr2 не достиг ptr1, попробуйте следующий узел после ptr1 * /

        ptr1 = ptr1->next;

    }

  

    / * После окончания цикла ptr2 является последним узлом цикла. Так

     сделать следующий из ptr2 как NULL * /

    ptr2->next = NULL;

}

  
/ * Функция для печати связанного списка * /

void printList(struct Node* node)

{

    while (node != NULL) {

        cout << node->data << " ";

        node = node->next;

    }

}

  

struct Node* newNode(int key)

{

    struct Node* temp = new Node();

    temp->data = key;

    temp->next = NULL;

    return temp;

}

  
// Код драйвера

int main()

{

    struct Node* head = newNode(50);

    head->next = newNode(20);

    head->next->next = newNode(15);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(10);

  

    / * Создать цикл для тестирования * /

    head->next->next->next->next->next = head->next->next;

  

    detectAndRemoveLoop(head);

  

    cout << "Linked List after removing loop" << endl;

  

    printList(head);

  

    return 0;

}

  
// Этот код предоставлен Striver

С

// C программа для обнаружения и удаления петли в связанном списке
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел списка ссылок * /

struct Node {

    int data;

    struct Node* next;

};

  
/ * Функция для удаления петли. Используется обнаружениемAndRemoveLoop () * /

void removeLoop(struct Node*, struct Node*);

  
/ * Эта функция обнаруживает и удаляет цикл в списке

  Если цикл был в списке, он возвращает 1,

  в противном случае возвращает 0 * /

int detectAndRemoveLoop(struct Node* list)

{

    struct Node *slow_p = list, *fast_p = list;

  

    while (slow_p && fast_p && fast_p->next) {

        slow_p = slow_p->next;

        fast_p = fast_p->next->next;

  

        / * Если slow_p и fast_p встречаются в какой-то момент, то есть

           это петля * /

        if (slow_p == fast_p) {

            removeLoop(slow_p, list);

  

            / * Вернуть 1, чтобы указать, что цикл найден * /

            return 1;

        }

    }

  

    / * Вернуть 0, чтобы выяснить, нет ли петли * /

    return 0;

}

  
/ * Функция для удаления петли.

 loop_node -> указатель на один из узлов цикла

 head -> Указатель на начальный узел связанного списка * /

void removeLoop(struct Node* loop_node, struct Node* head)

{

    struct Node* ptr1;

    struct Node* ptr2;

  

    / * Установить указатель на исправление связанного списка и

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

      часть связанного списка * /

    ptr1 = head;

    while (1) {

        / * Теперь запустите указатель из loop_node и проверьте, если он когда-либо

       достигает ptr2 * /

        ptr2 = loop_node;

        while (ptr2->next != loop_node && ptr2->next != ptr1)

            ptr2 = ptr2->next;

  

        / * Если ptr2 поменял ptr1, то есть цикл. Так сломай

        цикл * /

        if (ptr2->next == ptr1)

            break;

  

        / * Если ptr2 не достиг ptr1, попробуйте следующий узел после ptr1 * /

        ptr1 = ptr1->next;

    }

  

    / * После окончания цикла ptr2 является последним узлом цикла. Так

     сделать следующий из ptr2 как NULL * /

    ptr2->next = NULL;

}

  
/ * Функция для печати связанного списка * /

void printList(struct Node* node)

{

    while (node != NULL) {

        printf("%d  ", node->data);

        node = node->next;

    }

}

  

struct Node* newNode(int key)

{

    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

    temp->data = key;

    temp->next = NULL;

    return temp;

}

  
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    struct Node* head = newNode(50);

    head->next = newNode(20);

    head->next->next = newNode(15);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(10);

  

    / * Создать цикл для тестирования * /

    head->next->next->next->next->next = head->next->next;

  

    detectAndRemoveLoop(head);

  

    printf("Linked List after removing loop \n");

    printList(head);

    return 0;

}

Джава

// Java-программа для обнаружения и удаления цикла в связанном списке

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Функция, которая обнаруживает петлю в списке

    int detectAndRemoveLoop(Node node)

    {

        Node slow = node, fast = node;

        while (slow != null && fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

  

            // Если медленные и быстрые встречаются в одной и той же точке, то присутствует цикл

            if (slow == fast) {

                removeLoop(slow, node);

                return 1;

            }

        }

        return 0;

    }

  

    // Функция для удаления цикла

    void removeLoop(Node loop, Node curr)

    {

        Node ptr1 = null, ptr2 = null;

  

        / * Установить указатель на исправление связанного списка и

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

         часть связанного списка * /

        ptr1 = curr;

        while (1 == 1) {

  

            / * Теперь запустите указатель из loop_node и проверьте, если он когда-либо

             достигает ptr2 * /

            ptr2 = loop;

            while (ptr2.next != loop && ptr2.next != ptr1) {

                ptr2 = ptr2.next;

            }

  

            / * Если ptr2 поменял ptr1, то есть цикл. Так сломай

             цикл * /

            if (ptr2.next == ptr1) {

                break;

            }

  

            / * Если ptr2 не достиг ptr1, попробуйте следующий узел после ptr1 * /

            ptr1 = ptr1.next;

        }

  

        / * После окончания цикла ptr2 является последним узлом цикла. Так

         сделать следующий из ptr2 как NULL * /

        ptr2.next = null;

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

  

        // Создание цикла для тестирования

        head.next.next.next.next.next = head.next.next;

        list.detectAndRemoveLoop(head);

        System.out.println("Linked List after removing loop : ");

        list.printList(head);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

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

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    def detectAndRemoveLoop(self):

        slow_p = fast_p = self.head

        while(slow_p and fast_p and fast_p.next):

            slow_p = slow_p.next 

            fast_p = fast_p.next.next

          

            # Если slow_p и fast_p встречаются в некоторой точке

            # тогда есть цикл

            if slow_p == fast_p:

                self.removeLoop(slow_p)

                  

                # Вернуть 1, чтобы указать, что цикл, если найден

                return 1 

  

        # Вернуть 0, чтобы указать, что петли нет

        return 0

  

    # Функция для удаления цикла

    # loop node-> Указатель на один из узлов цикла

    # head -> Указатель на начальный узел

    # связанный список

    def removeLoop(self, loop_node):

          

        # Установить указатель на начало связанного

        # список и переместить его по очереди, чтобы найти первый

        # узел, который является частью связанного списка

        ptr1 = self.head

        while(1):

            # Теперь запустите указатель из loop_node и проверьте

            # если он когда-либо достигнет ptr2

            ptr2 = loop_node

            while(ptr2.next != loop_node and ptr2.next != ptr1):

                ptr2 = ptr2.next

              

            # Если ptr2 достиг ptr1, то есть цикл.

            # Так что разорвать петлю

            if ptr2.next == ptr1 : 

                break 

              

            ptr1 = ptr1.next

          

        # После окончания цикла ptr2 является узлом lsat

        # петля. Так что сделайте следующий из ptr2 как NULL

        ptr2.next = None

    # Функция для вставки нового узла в начале

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

  
# Драйверная программа

llist = LinkedList()

llist.push(10)

llist.push(4)

llist.push(15)

llist.push(20)

llist.push(50)

  
# Создать цикл для тестирования

llist.head.next.next.next.next.next = llist.head.next.next

  
llist.detectAndRemoveLoop()

  

print "Linked List after removing loop"

llist.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для обнаружения и удаления цикла в связанном списке

using System;

  

public class LinkedList {

  

    public Node head;

  

    public class Node {

  

        public int data;

        public Node next;

  

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Функция, которая обнаруживает петлю в списке

    int detectAndRemoveLoop(Node node)

    {

        Node slow = node, fast = node;

        while (slow != null && fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

  

            // Если медленные и быстрые встречаются в одной и той же точке, то присутствует цикл

            if (slow == fast) {

                removeLoop(slow, node);

                return 1;

            }

        }

        return 0;

    }

  

    // Функция для удаления цикла

    void removeLoop(Node loop, Node curr)

    {

        Node ptr1 = null, ptr2 = null;

  

        / * Установить указатель на исправление связанного списка и

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

         часть связанного списка * /

        ptr1 = curr;

        while (1 == 1) {

  

            / * Теперь запустите указатель из loop_node и проверьте, если он когда-либо

             достигает ptr2 * /

            ptr2 = loop;

            while (ptr2.next != loop && ptr2.next != ptr1) {

                ptr2 = ptr2.next;

            }

  

            / * Если ptr2 поменял ptr1, то есть цикл. Так сломай

             цикл * /

            if (ptr2.next == ptr1) {

                break;

            }

  

            / * Если ptr2 не достиг ptr1, попробуйте следующий узел после ptr1 * /

            ptr1 = ptr1.next;

        }

  

        / * После окончания цикла ptr2 является последним узлом цикла. Так

         сделать следующий из ptr2 как NULL * /

        ptr2.next = null;

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            Console.Write(node.data + " ");

            node = node.next;

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

  

        // Создание цикла для тестирования

        list.head.next.next.next.next.next = list.head.next.next;

        list.detectAndRemoveLoop(list.head);

        Console.WriteLine("Linked List after removing loop : ");

        list.printList(list.head);

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Linked List after removing loop 
50 20 15 4 10 

Метод 2 (лучшее решение)

  1. Этот метод также зависит от алгоритма обнаружения циклов Флойда.
  2. Обнаружение цикла с использованием алгоритма обнаружения цикла Флойда и получение указателя на узел цикла.
  3. Подсчитайте количество узлов в цикле. Пусть счет будет k.
  4. Закрепите один указатель на голове, а другой — на k-м узле от головы.
  5. Перемещайте оба указателя в одинаковом темпе, они встретятся в начальном узле цикла.
  6. Получить указатель на последний узел цикла и сделать следующий из него как NULL.

Спасибо WgpShashank за предложение этого метода.

Ниже на рисунке показан пробный запуск функции «удалить цикл» в коде:

Ниже приведена реализация вышеуказанного подхода:

CPP

#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

struct Node {

    int data;

    struct Node* next;

};

  
/ * Функция для удаления петли. * /

void removeLoop(struct Node*, struct Node*);

  
/ * Эта функция обнаруживает и удаляет цикл в списке

  Если цикл был в списке, он возвращает 1,

  в противном случае возвращает 0 * /

int detectAndRemoveLoop(struct Node* list)

{

    struct Node *slow_p = list, *fast_p = list;

  

    // Итерация и поиск, если цикл существует или нет

    while (slow_p && fast_p && fast_p->next) {

        slow_p = slow_p->next;

        fast_p = fast_p->next->next;

  

        / * Если slow_p и fast_p встречаются в какой-то момент, то есть

           это петля * /

        if (slow_p == fast_p) {

            removeLoop(slow_p, list);

  

            / * Вернуть 1, чтобы указать, что цикл найден * /

            return 1;

        }

    }

  

    / * Вернуть 0, чтобы выяснить, нет ли петли * /

    return 0;

}

  
/ * Функция для удаления петли.

 loop_node -> указатель на один из узлов цикла

 head -> Указатель на начальный узел связанного списка * /

void removeLoop(struct Node* loop_node, struct Node* head)

{

    struct Node* ptr1 = loop_node;

    struct Node* ptr2 = loop_node;

  

    // Подсчитать количество узлов в цикле

    unsigned int k = 1, i;

    while (ptr1->next != ptr2) {

        ptr1 = ptr1->next;

        k++;

    }

  

    // Исправить один указатель на голову

    ptr1 = head;

  

    // И другой указатель на k узлов после головы

    ptr2 = head;

    for (i = 0; i < k; i++)

        ptr2 = ptr2->next;

  

    / * Перемещайте оба указателя в одинаковом темпе,

      они встретятся в начальном узле цикла * /

    while (ptr2 != ptr1) {

        ptr1 = ptr1->next;

        ptr2 = ptr2->next;

    }

  

    // Получить указатель на последний узел

    while (ptr2->next != ptr1)

        ptr2 = ptr2->next;

  

    / * Установить следующий узел конечного узла цикла

      исправить петлю * /

    ptr2->next = NULL;

}

  
/ * Функция для печати связанного списка * /

void printList(struct Node* node)

{

    // Распечатать список после удаления цикла

    while (node != NULL) {

        cout << node->data << " ";

        node = node->next;

    }

}

  

struct Node* newNode(int key)

{

    struct Node* temp = new Node();

    temp->data = key;

    temp->next = NULL;

    return temp;

}

  
// Код драйвера

int main()

{

    struct Node* head = newNode(50);

    head->next = newNode(20);

    head->next->next = newNode(15);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(10);

  

    / * Создать цикл для тестирования * /

    head->next->next->next->next->next = head->next->next;

  

    detectAndRemoveLoop(head);

  

    cout << "Linked List after removing loop \n";

    printList(head);

    return 0;

}

  
// Этот код предоставлен Striver

С

#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

struct Node {

    int data;

    struct Node* next;

};

  
/ * Функция для удаления петли. * /

void removeLoop(struct Node*, struct Node*);

  
/ * Эта функция обнаруживает и удаляет цикл в списке

  Если цикл был в списке, он возвращает 1,

  в противном случае возвращает 0 * /

int detectAndRemoveLoop(struct Node* list)

{

    struct Node *slow_p = list, *fast_p = list;

  

    // Итерация и поиск, если цикл существует или нет

    while (slow_p && fast_p && fast_p->next) {

        slow_p = slow_p->next;

        fast_p = fast_p->next->next;

  

        / * Если slow_p и fast_p встречаются в какой-то момент, то есть

           это петля * /

        if (slow_p == fast_p) {

            removeLoop(slow_p, list);

  

            / * Вернуть 1, чтобы указать, что цикл найден * /

            return 1;

        }

    }

  

    / * Вернуть 0, чтобы выяснить, нет ли петли * /

    return 0;

}

  
/ * Функция для удаления петли.

 loop_node -> указатель на один из узлов цикла

 head -> Указатель на начальный узел связанного списка * /

void removeLoop(struct Node* loop_node, struct Node* head)

{

    struct Node* ptr1 = loop_node;

    struct Node* ptr2 = loop_node;

  

    // Подсчитать количество узлов в цикле

    unsigned int k = 1, i;

    while (ptr1->next != ptr2) {

        ptr1 = ptr1->next;

        k++;

    }

  

    // Исправить один указатель на голову

    ptr1 = head;

  

    // И другой указатель на k узлов после головы

    ptr2 = head;

    for (i = 0; i < k; i++)

        ptr2 = ptr2->next;

  

    / * Перемещайте оба указателя в одинаковом темпе,

      они встретятся в начальном узле цикла * /

    while (ptr2 != ptr1) {

        ptr1 = ptr1->next;

        ptr2 = ptr2->next;

    }

  

    // Получить указатель на последний узел

    while (ptr2->next != ptr1)

        ptr2 = ptr2->next;

  

    / * Установить следующий узел конечного узла цикла

      исправить петлю * /

    ptr2->next = NULL;

}

  
/ * Функция для печати связанного списка * /

void printList(struct Node* node)

{

    // Распечатать список после удаления цикла

    while (node != NULL) {

        cout << node->data << " ";

        node = node->next;

    }

}

  

struct Node* newNode(int key)

{

    struct Node* temp = new Node();

    temp->data = key;

    temp->next = NULL;

    return temp;

}

  
// Код драйвера

int main()

{

    struct Node* head = newNode(50);

    head->next = newNode(20);

    head->next->next = newNode(15);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(10);

  

    / * Создать цикл для тестирования * /

    head->next->next->next->next->next = head->next->next;

  

    detectAndRemoveLoop(head);

  

    cout << "Linked List after removing loop \n";

    printList(head);

    return 0;

}

  
// Этот код предоставлен Striver

Джава

// Java-программа для обнаружения и удаления цикла в связанном списке

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Функция, которая обнаруживает петлю в списке

    int detectAndRemoveLoop(Node node)

    {

        Node slow = node, fast = node;

        while (slow != null && fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

  

            // Если медленные и быстрые встречаются в одной и той же точке, то присутствует цикл

            if (slow == fast) {

                removeLoop(slow, node);

                return 1;

            }

        }

        return 0;

    }

  

    // Функция для удаления цикла

    void removeLoop(Node loop, Node head)

    {

        Node ptr1 = loop;

        Node ptr2 = loop;

  

        // Подсчитать количество узлов в цикле

        int k = 1, i;

        while (ptr1.next != ptr2) {

            ptr1 = ptr1.next;

            k++;

        }

  

        // Исправить один указатель на голову

        ptr1 = head;

  

        // И другой указатель на k узлов после головы

        ptr2 = head;

        for (i = 0; i < k; i++) {

            ptr2 = ptr2.next;

        }

  

        / * Перемещайте оба указателя в одинаковом темпе,

         они встретятся в начальном узле цикла * /

        while (ptr2 != ptr1) {

            ptr1 = ptr1.next;

            ptr2 = ptr2.next;

        }

  

        // Получить указатель на последний узел

        while (ptr2.next != ptr1) {

            ptr2 = ptr2.next;

        }

  

        / * Установить следующий узел конечного узла цикла

         исправить петлю * /

        ptr2.next = null;

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

  

        // Создание цикла для тестирования

        head.next.next.next.next.next = head.next.next;

        list.detectAndRemoveLoop(head);

        System.out.println("Linked List after removing loop : ");

        list.printList(head);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

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

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    def detectAndRemoveLoop(self):

        slow_p = fast_p = self.head

          

        while(slow_p and fast_p and fast_p.next):

            slow_p = slow_p.next

            fast_p = fast_p.next.next

  

            # Если в какой-то момент встретятся slow_p и fast_p, то

            # есть цикл

            if slow_p == fast_p:

                self.removeLoop(slow_p)

          

                # Возврат 1, чтобы указать, что цикл найден

                return 1

          

        # Вернуть 0, чтобы указать, что петли нет

        return 0 

  

    # Функция для удаления цикла

    # loop_node -> указатель на один из узлов цикла

    # head -> Указатель на начальный узел связанного списка

    def removeLoop(self, loop_node):

        ptr1 = loop_node

        ptr2 = loop_node

          

        # Подсчитать количество узлов в цикле

        k = 1 

        while(ptr1.next != ptr2):

            ptr1 = ptr1.next

            k += 1

  

        # Исправить один указатель на голову

        ptr1 = self.head

          

        # И другой указатель на k узлов после головы

        ptr2 = self.head

        for i in range(k):

            ptr2 = ptr2.next

  

        # Переместить оба указателя в одном месте

        # они встретятся в начальном узле цикла

        while(ptr2 != ptr1):

            ptr1 = ptr1.next

            ptr2 = ptr2.next

  

        # Получить указатель на последний узел

        while(ptr2.next != ptr1):

            ptr2 = ptr2.next

  

        # Установить следующий узел конечного узла цикла

        # исправить цикл

        ptr2.next = None

  

    # Функция для вставки нового узла в начале

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

  
# Драйверная программа

llist = LinkedList()

llist.push(10)

llist.push(4)

llist.push(15)

llist.push(20)

llist.push(50)

  
# Создать цикл для тестирования

llist.head.next.next.next.next.next = llist.head.next.next

  
llist.detectAndRemoveLoop()

  

print "Linked List after removing loop"

llist.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// AC # программа для обнаружения и удаления петли в связанном списке

using System;

public class LinkedList {

  

    Node head;

  

    public class Node {

  

        public int data;

        public Node next;

  

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Функция, которая обнаруживает петлю в списке

    int detectAndRemoveLoop(Node node)

    {

        Node slow = node, fast = node;

        while (slow != null && fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

  

            // Если медленно и быстро встречаются одновременно

            // точка, то цикл присутствует

            if (slow == fast) {

                removeLoop(slow, node);

                return 1;

            }

        }

        return 0;

    }

  

    // Функция для удаления цикла

    void removeLoop(Node loop, Node head)

    {

        Node ptr1 = loop;

        Node ptr2 = loop;

  

        // Подсчитать количество узлов в цикле

        int k = 1, i;

        while (ptr1.next != ptr2) {

            ptr1 = ptr1.next;

            k++;

        }

  

        // Исправить один указатель на голову

        ptr1 = head;

  

        // И другой указатель на k узлов после головы

        ptr2 = head;

        for (i = 0; i < k; i++) {

            ptr2 = ptr2.next;

        }

  

        / * Перемещайте оба указателя в одинаковом темпе,

        они встретятся в начальном узле цикла * /

        while (ptr2 != ptr1) {

            ptr1 = ptr1.next;

            ptr2 = ptr2.next;

        }

  

        // Получить указатель на последний узел

        while (ptr2.next != ptr1) {

            ptr2 = ptr2.next;

        }

  

        / * Установить следующий узел конечного узла цикла

        исправить петлю * /

        ptr2.next = null;

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            Console.Write(node.data + " ");

            node = node.next;

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

  

        // Создание цикла для тестирования

        list.head.next.next.next.next.next = list.head.next.next;

        list.detectAndRemoveLoop(list.head);

        Console.WriteLine("Linked List after removing loop : ");

        list.printList(list.head);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Linked List after removing loop 
50 20 15 4 10 

Метод 3 (Оптимизированный метод 2: без подсчета узлов в цикле)
Нам не нужно считать количество узлов в цикле. После обнаружения цикла, если мы запустим медленный указатель с головы и будем перемещать как медленные, так и быстрые указатели с одинаковой скоростью, пока быстрый не встретится, они встретятся в начале цикла.

Как это работает?
Пусть медленные и быстрые встретятся в какой-то момент после алгоритма поиска Цикла Флойда. На диаграмме ниже показана ситуация, когда цикл найден.

Мы можем сделать вывод из приведенной выше диаграммы


Distance traveled by fast pointer = 2 * (Distance traveled 
                                         by slow pointer)

(m + n*x + k) = 2*(m + n*y + k)

Note that before meeting the point shown above, fast
was moving at twice speed.

x -->  Number of complete cyclic rounds made by 
       fast pointer before they meet first time

y -->  Number of complete cyclic rounds made by 
       slow pointer before they meet first time

Из приведенного выше уравнения можно сделать вывод ниже

    m + k = (x-2y)*n

Which means m+k is a multiple of n. 

Таким образом, если мы начнем снова перемещать оба указателя с одинаковой скоростью , так что один указатель (скажем, медленный) начинается с головного узла связанного списка, а другой указатель (скажем, быстрый) начинается с точки встречи. Когда медленный указатель достигает начала цикла (сделал m шагов), быстрый указатель также сделал бы m шагов, поскольку теперь они движутся с одинаковой скоростью. Поскольку m + k кратно n и быстрый старт начинается с k, они встречаются в начале. Могут ли они встретиться раньше? Нет, потому что медленный указатель входит в цикл впервые после m шагов.

C ++

// C ++ программа для обнаружения и удаления цикла
#include <bits/stdc++.h>

using namespace std;

  

struct Node {

    int key;

    struct Node* next;

};

  

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    temp->next = NULL;

    return temp;

}

  
// Утилита для печати связанного списка

void printList(Node* head)

{

    while (head != NULL) {

        cout << head->key << " ";

        head = head->next;

    }

    cout << endl;

}

  
// Функция для обнаружения и удаления петли
// в связанном списке, который может содержать цикл

void detectAndRemoveLoop(Node* head)

{

    // Если список пуст или имеет только один узел

    // без цикла

    if (head == NULL || head->next == NULL)

        return;

  

    Node *slow = head, *fast = head;

  

    // Двигаемся медленно и быстро на 1 и 2 шага

    // впереди соответственно.

    slow = slow->next;

    fast = fast->next->next;

  

    // Поиск цикла с использованием медленных и

    // быстрые указатели

    while (fast && fast->next) {

        if (slow == fast)

            break;

        slow = slow->next;

        fast = fast->next->next;

    }

  

    / * Если цикл существует * /

    if (slow == fast) {

        slow = head;

        while (slow->next != fast->next) {

            slow = slow->next;

            fast = fast->next;

        }

  

        / * поскольку fast-> next является точкой цикла * /

        fast->next = NULL; / * удалить цикл * /

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    Node* head = newNode(50);

    head->next = head;

    head->next = newNode(20);

    head->next->next = newNode(15);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(10);

  

    / * Создать цикл для тестирования * /

    head->next->next->next->next->next = head->next->next;

  

    detectAndRemoveLoop(head);

  

    printf("Linked List after removing loop \n");

    printList(head);

  

    return 0;

}

Джава

// Java-программа для обнаружения и удаления цикла в связанном списке

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Функция, которая обнаруживает петлю в списке

    void detectAndRemoveLoop(Node node)

    {

  

        // Если список пуст или имеет только один узел

        // без цикла

        if (node == null || node.next == null)

            return;

  

        Node slow = node, fast = node;

  

        // Двигаемся медленно и быстро на 1 и 2 шага

        // впереди соответственно.

        slow = slow.next;

        fast = fast.next.next;

  

        // Поиск цикла с использованием медленных и быстрых указателей

        while (fast != null && fast.next != null) {

            if (slow == fast)

                break;

  

            slow = slow.next;

            fast = fast.next.next;

        }

  

        / * Если цикл существует * /

        if (slow == fast) {

            slow = node;

            while (slow.next != fast.next) {

                slow = slow.next;

                fast = fast.next;

            }

  

            / * поскольку fast-> next является точкой цикла * /

            fast.next = null; / * удалить цикл * /

        }

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

  

        // Создание цикла для тестирования

        head.next.next.next.next.next = head.next.next;

        list.detectAndRemoveLoop(head);

        System.out.println("Linked List after removing loop : ");

        list.printList(head);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

# Python программа для обнаружения и удаления цикла

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    # Функция для вставки нового узла в начале

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

     

    def detectAndRemoveLoop(self):

  

        if self.head is None :

            return

        if self.head.next is None :

            return

  

        slow = self.head 

        fast = self.head

  

        # Двигайтесь медленно и быстро на 1 и 2 шага соответственно

        slow = slow.next

        fast = fast.next.next

  

        # Поиск цикла с использованием медленных и быстрых указателей

        while (fast is not None):

            if fast.next is None:

                break 

            if slow == fast :

                break

            slow = slow.next

            fast = fast.next.next

  

        # если цикл существует

        if slow == fast :

            slow = self.head

            while (slow.next != fast.next):

                slow = slow.next

                fast = fast.next

              

            # Sinc fast.next - точка цикла

            fast.next = None # Удалить цикл

  

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

  
# Драйверная программа

llist = LinkedList()

llist.head = Node(50)

llist.head.next = Node(20)

llist.head.next.next = Node(15)

llist.head.next.next.next = Node(4)

llist.head.next.next.next.next = Node(10)

  
# Создать цикл для тестирования

llist.head.next.next.next.next.next = llist.head.next.next

  
llist.detectAndRemoveLoop()

  

print "Linked List after removing loop"

llist.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для обнаружения и удаления цикла в связанном списке

using System;

  

public class LinkedList {

  

    public Node head;

  

    public class Node {

  

        public int data;

        public Node next;

  

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Функция, которая обнаруживает петлю в списке

    void detectAndRemoveLoop(Node node)

    {

  

        // Если список пуст или имеет только один узел

        // без цикла

        if (node == null || node.next == null)

            return;

  

        Node slow = node, fast = node;

  

        // Двигаемся медленно и быстро на 1 и 2 шага

        // впереди соответственно.

        slow = slow.next;

        fast = fast.next.next;

  

        // Поиск цикла с использованием медленных и быстрых указателей

        while (fast != null && fast.next != null) {

            if (slow == fast)

                break;

  

            slow = slow.next;

            fast = fast.next.next;

        }

  

        / * Если цикл существует * /

        if (slow == fast) {

            slow = node;

            while (slow.next != fast.next) {

                slow = slow.next;

                fast = fast.next;

            }

  

            / * поскольку fast-> next является точкой цикла * /

            fast.next = null; / * удалить цикл * /

        }

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            Console.Write(node.data + " ");

            node = node.next;

        }

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(50);

        list.head.next = new Node(20);

        list.head.next.next = new Node(15);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(10);

  

        // Создание цикла для тестирования

        list.head.next.next.next.next.next = list.head.next.next;

        list.detectAndRemoveLoop(list.head);

        Console.WriteLine("Linked List after removing loop : ");

        list.printList(list.head);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Linked List after removing loop 
50 20 15 4 10 

Метод 4: хеширование: хеширование адреса узлов связанного списка
Мы можем хэшировать адреса узлов связанного списка в неупорядоченной карте и просто проверять, существует ли элемент на карте. Если он существует, мы достигли узла, который уже существует циклом, поэтому нам нужно сделать следующий указатель последнего узла NULL.

C ++

// C ++ программа для обнаружения и удаления цикла
#include <bits/stdc++.h>

using namespace std;

  

struct Node {

    int key;

    struct Node* next;

};

  

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    temp->next = NULL;

    return temp;

}

  
// Утилита для печати связанного списка

void printList(Node* head)

{

    while (head != NULL) {

        cout << head->key << " ";

        head = head->next;

    }

    cout << endl;

}

  
// Функция для обнаружения и удаления петли
// в связанном списке, который может содержать цикл

void hashAndRemove(Node* head)

{

    // отображение хеша на адреса хеша узлов связанного списка

    unordered_map<Node*, int> node_map;

    // указатель на последний узел

    Node* last = NULL;

    while (head != NULL) {

        // если узел не присутствует на карте, вставить его в карту

        if (node_map.find(head) == node_map.end()) {

            node_map[head]++;

            last = head;

            head = head->next;

        }

        // если присутствует, это цикл, сделать следующий указатель последнего узла NULL

        else {

            last->next = NULL;

            break;

        }

    }

}
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    Node* head = newNode(50);

    head->next = head;

    head->next = newNode(20);

    head->next->next = newNode(15);

    head->next->next->next = newNode(4);

    head->next->next->next->next = newNode(10);

  

    / * Создать цикл для тестирования * /

    head->next->next->next->next->next = head->next->next;

  

    // printList (head);

    hashAndRemove(head);

  

    printf("Linked List after removing loop \n");

    printList(head);

  

    return 0;

}

Джава

// Java-программа для обнаружения и удаления цикла в связанном списке

import java.util.*;

  

public class LinkedList {

  

    static Node head; // заголовок списка

  

    / * Узел связанного списка * /

    static class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Вставляет новый узел в начало списка. * /

    static public void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    // Функция для печати связанного списка

    void printList(Node node)

    {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    // Возвращает true, если цикл удален из связанного

    // list else возвращает false.

    static boolean removeLoop(Node h)

    {

        HashSet<Node> s = new HashSet<Node>();

        Node prev = null;

        while (h != null) {

            // Если у нас уже есть этот узел

            // в hashmap это означает, что это цикл, и мы

            // необходимо удалить этот цикл, поэтому установите следующий из

            // предыдущий указатель с нулем.

  

            if (s.contains(h)) {

                prev.next = null;

                return true;

            }

  

            // Если мы видим узел для

            // первый раз вставить в хеш

            else {

                s.add(h);

                prev = h;

                h = h.next;

            }

        }

  

        return false;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

  

        llist.push(20);

        llist.push(4);

        llist.push(15);

        llist.push(10);

  

        / * Создать цикл для тестирования * /

        llist.head.next.next.next.next = llist.head;

  

        if (removeLoop(head)) {

            System.out.println("Linked List after removing loop");

            llist.printList(head);

        }

        else

            System.out.println("No Loop found");

    }

}

  
// Этот код предоставлен Animesh Nag.

Мы благодарим Шубхам Агравал за предложение этого решения.

Спасибо Gaurav Ahirwar за предложенное выше решение.

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

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

0.00 (0%) 0 votes