Рубрики

Определить петлю в связанном списке

Имея связанный список, проверьте, есть ли в связанном списке цикл или нет. На диаграмме ниже показан связанный список с циклом.

Ниже приведены различные способы сделать это
Используйте Хеширование:
Обходите список по одному и продолжайте помещать адреса узлов в хэш-таблицу. В любой момент, если достигается значение NULL, вернуть false, а если следующий из текущего узла указывает на какой-либо из ранее сохраненных узлов в Hash, вернуть true.

C ++

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

using namespace std;

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

struct Node {

    int data;

    struct Node* next;

};

  

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node = new Node;

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

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

    (*head_ref) = new_node;

}

  
// Возвращает true, если в связанном списке есть цикл
// иначе возвращает false.

bool detectLoop(struct Node* h)

{

    unordered_set<Node*> s;

    while (h != NULL) {

        // Если этот узел уже присутствует

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

        // (Потому что вы встречаете

        // узел во второй раз).

        if (s.find(h) != s.end())

            return true;

  

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

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

        s.insert(h);

  

        h = h->next;

    }

  

    return false;

}

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

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    push(&head, 20);

    push(&head, 4);

    push(&head, 15);

    push(&head, 10);

  

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

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

  

    if (detectLoop(head))

        cout << "Loop found";

    else

        cout << "No Loop";

  

    return 0;

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

Джава

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

    }

  

    // Возвращает true, если в связанном цикле есть

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

    static boolean detectLoop(Node h)

    {

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

        while (h != null) {

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

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

            // (Потому что вы встречаете

            // узел второй раз).

            if (s.contains(h))

                return true;

  

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

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

            s.add(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 (detectLoop(head))

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

        else

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

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# 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

   

    # Утилита для печати

    # связанный LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print (temp.data, end =" ")

            temp = temp.next

   

   

    def detectLoop(self):

         s = set()

         temp = self.head

         while (temp):

          

             # Если у нас уже есть

             # этот узел в hashmap это

             # означает, что это цикл

             # (Потому что с тобой мы сталкиваемся

             # узел второй раз).

            if (temp in s):

                return True

     

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

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

            s.add(temp)

     

            temp = temp.next

          

     

         return False

   
# Драйвер программы для тестирования

llist = LinkedList()

llist.push(20)

llist.push(4)

llist.push(15)

llist.push(10)

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

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

  

if( llist.detectLoop()):

    print ("Loop found")

else :

    print ("No Loop ")

  
# Этот код предоставлен Gitanjali.

C #

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

using System;

using System.Collections.Generic;

  

class LinkedList {

  

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

  

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

    public class Node {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

    public void push(int new_data)

    {

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

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

        Node new_node = new Node(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

    // Возвращает true, если в связанном цикле есть

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

    public static bool detectLoop(Node h)

    {

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

        while (h != null) {

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

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

            // (Потому что вы встречаете

            // узел второй раз).

            if (s.Contains(h))

                return true;

  

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

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

            s.Add(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 (detectLoop(llist.head))

            Console.WriteLine("Loop found");

        else

            Console.WriteLine("No Loop");

    }

}

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

Выход:

Loop found

Подход с использованием отмеченных посещенных узлов. Это решение требует изменений в базовой структуре данных связанного списка.

  • Имейте посещенный флаг с каждым узлом.
  • Пройдите по связанному списку и продолжайте отмечать посещенные узлы.
  • Если вы снова видите посещенный узел, то есть цикл. Это решение работает в O (n), но требует дополнительной информации с каждого узла.
  • Вариант этого решения, который не требует модификации базовой структуры данных, может быть реализован с использованием хэша, просто храните адреса посещенных узлов в хэше, и если вы видите адрес, который уже существует в хэше, то возникает цикл
  • ,

Алгоритм нахождения цикла Флойда: это самый быстрый метод, который был описан ниже:

  • Пройдите по связанному списку, используя два указателя.
  • Переместите один указатель (slow_p) на один, а другой указатель (fast_p) на два.
  • Если эти указатели встречаются в одном и том же узле, то существует цикл. Если указатели не встречаются, то связанный список не имеет цикла
  • ,

На рисунке ниже показано, как работает функция deteloop в коде:

Реализация алгоритма поиска циклов Флойда:

C ++

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

using namespace std;

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

class Node {

public:

    int data;

    Node* next;

};

  

void push(Node** head_ref, int new_data)

{

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

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

    (*head_ref) = new_node;

}

  

int detectloop(Node* list)

{

    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;

        if (slow_p == fast_p) {

            cout << "Found Loop";

            return 1;

        }

    }

    return 0;

}

  
/ * Код водителя * /

int main()

{

    / * Начнем с пустого списка * /

    Node* head = NULL;

  

    push(&head, 20);

    push(&head, 4);

    push(&head, 15);

    push(&head, 10);

  

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

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

    detectloop(head);

  

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

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

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

struct Node {

    int data;

    struct Node* next;

};

  

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

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

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

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

    (*head_ref) = new_node;

}

  

int detectloop(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;

        if (slow_p == fast_p) {

            printf("Found Loop");

            return 1;

        }

    }

    return 0;

}

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

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    push(&head, 20);

    push(&head, 4);

    push(&head, 15);

    push(&head, 10);

  

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

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

    detectloop(head);

  

    return 0;

}

Джава

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

class LinkedList {

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

  

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

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

    public void push(int new_data)

    {

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

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

        Node new_node = new Node(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

    int detectLoop()

    {

        Node slow_p = head, fast_p = head;

        while (slow_p != null && fast_p != null && fast_p.next != null) {

            slow_p = slow_p.next;

            fast_p = fast_p.next.next;

            if (slow_p == fast_p) {

                System.out.println("Found loop");

                return 1;

            }

        }

        return 0;

    }

  

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

    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;

  

        llist.detectLoop();

    }

}
/ * Этот код предоставлен Раджатом Мишрой. * /

питон

# 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

  

    # Сервисная функция, чтобы напечатать это связанный LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

  

    def detectLoop(self):

        slow_p = self.head

        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

            if slow_p == fast_p:

                print "Found Loop"

                return 

  
# Драйвер программы для тестирования

llist = LinkedList()

llist.push(20)

llist.push(4)

llist.push(15)

llist.push(10)

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

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

llist.detectLoop()

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

C #

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

using System;

  

public class LinkedList 

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

  

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

    public class Node 

    

        public int data; 

        public Node next; 

        public Node(int d) 

        

            data = d; 

            next = null

        

    

  

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

    public void push(int new_data) 

    

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

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

        Node new_node = new Node(new_data); 

  

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

        new_node.next = head; 

  

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

        head = new_node; 

    

  

    int detectLoop() 

    

        Node slow_p = head, fast_p = head; 

        while (slow_p != null && fast_p != null &&

                                fast_p.next != null)

        

            slow_p = slow_p.next; 

            fast_p = fast_p.next.next; 

            if (slow_p == fast_p)

            

                Console.WriteLine("Found loop"); 

                return 1; 

            

        

        return 0; 

    

  

    / * Код водителя * /

    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; 

  

        llist.detectLoop(); 

    

  
// Этот код предоставлен Принчи Сингхом

Выход:

Found Loop

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Как работает вышеуказанный алгоритм?
Пожалуйста, смотрите: Как работают медленные и быстрые указатели Флойда?

Ссылки:
http://en.wikipedia.org/wiki/Cycle_detection
http://ostermiller.org/find_loop_singly_linked_list.html

Пометка посещенных узлов без изменения структуры данных связанного списка
В этом методе создается временный узел. Следующий указатель каждого пройденного узла делается так, чтобы он указывал на этот временный узел. Таким образом, мы используем следующий указатель узла в качестве флага, чтобы указать, был ли пройден узел или нет. Каждый узел проверяется, чтобы увидеть, указывает ли следующий на временный узел или нет. В случае первого узла цикла, когда мы пройдем его второй раз, это условие будет выполнено, поэтому мы обнаружим, что цикл существует. Если мы сталкиваемся с узлом, который указывает на ноль, то цикл не существует.
Код выполняется за O (n) сложности времени и использует постоянное пространство памяти.

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

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;

}

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

bool detectLoop(Node* head)

{

  

    // Создать временный узел

    Node* temp = new Node;

    while (head != NULL) {

  

        // Это условие для случая

        // когда петли нет

        if (head->next == NULL) {

            return false;

        }

  

        // Проверить, если следующий уже

        // указывая на темп

        if (head->next == temp) {

            return true;

        }

  

        // Сохраняем указатель на следующий узел

        // чтобы перейти к следующему шагу

        Node* nex = head->next;

  

        // Сделать следующую точку для температуры

        head->next = temp;

  

        // Получить к следующему узлу в списке

        head = nex;

    }

  

    return false;

}

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

int main()

{

    Node* head = newNode(1);

    head->next = newNode(2);

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

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

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

  

    / * Создать цикл для тестирования (5 указывает на 3) * /

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

  

    bool found = detectLoop(head);

    if (found)

        cout << "Loop Found";

    else

        cout << "No Loop";

  

    return 0;

}

Джава

// Java-программа для возврата первого узла цикла

class GFG {

  

    static class Node {

        int key;

        Node next;

    };

  

    static Node newNode(int key)

    {

        Node temp = new Node();

        temp.key = key;

        temp.next = null;

        return temp;

    }

  

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

    static void printList(Node head)

    {

        while (head != null) {

            System.out.print(head.key + " ");

            head = head.next;

        }

        System.out.println();

    }

  

    // Функция для обнаружения первого узла цикла

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

    static boolean detectLoop(Node head)

    {

  

        // Создать временный узел

        Node temp = new Node();

        while (head != null) {

  

            // Это условие для случая

            // когда петли нет

            if (head.next == null) {

                return false;

            }

  

            // Проверить, если следующий уже

            // указывая на темп

            if (head.next == temp) {

                return true;

            }

  

            // Сохраняем указатель на следующий узел

            // чтобы перейти к следующему шагу

            Node nex = head.next;

  

            // Сделать следующую точку для температуры

            head.next = temp;

  

            // Получить к следующему узлу в списке

            head = nex;

        }

  

        return false;

    }

  

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

    public static void main(String args[])

    {

        Node head = newNode(1);

        head.next = newNode(2);

        head.next.next = newNode(3);

        head.next.next.next = newNode(4);

        head.next.next.next.next = newNode(5);

  

        // Создать цикл для тестирования (5 указывает на 3) /

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

  

        boolean found = detectLoop(head);

        if (found)

            System.out.println("Loop Found");

        else

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

    }

}

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 программа для возврата первого узла цикла

  
# Узел двоичного дерева содержит данные, указатель на
# левый ребенок и указатель на правый ребенок
# Вспомогательная функция, которая выделяет новый узел
# с заданными данными и ни один не осталось и
# правильные указатели

class newNode:

    def __init__(self, key):

        self.key= key

        self.left = None

        self.right = None

  
# Полезная функция для праа связанного списка

def printList(head):

    while (head != None):

        print(head.key, end = " ")

        head = head.next

      

    print()

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

def detectLoop( head):

  

    # Создать временный узел

    temp = ""

    while (head != None):

          

        # Это условие для случая

        # когда петли нет

        if (head.next == None):

            return False

              

        # Проверьте, если следующий уже

        # указывает на темп

        if (head.next == temp):

            return True

  

        # Сохранить указатель на следующий узел

        # чтобы перейти к следующему шагу

        nex = head.next

  

        # Создайте следующий темп

        head.next = temp

  

        # Перейти к следующему узлу в списке

        head = nex

  

    return False

  
Код водителя

head = newNode(1

head.next = newNode(2

head.next.next = newNode(3

head.next.next.next = newNode(4

head.next.next.next.next = newNode(5

  
# Создать цикл для тестирования (5 указывает на 3)

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

  

found = detectLoop(head) 

if (found):

    print("Loop Found")

else:

    print("No Loop")

  
# Этот код предоставлен SHUBHAMSINGH10

C #

// C # программа для возврата первого узла цикла

using System;

public class GFG {

  

    public class Node {

        public int key;

        public Node next;

    };

  

    static Node newNode(int key)

    {

        Node temp = new Node();

        temp.key = key;

        temp.next = null;

        return temp;

    }

  

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

    static void printList(Node head)

    {

        while (head != null) {

            Console.Write(head.key + " ");

            head = head.next;

        }

        Console.WriteLine();

    }

  

    // Функция для обнаружения первого узла цикла

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

    static Boolean detectLoop(Node head)

    {

  

        // Создать временный узел

        Node temp = new Node();

        while (head != null) {

  

            // Это условие для случая

            // когда петли нет

            if (head.next == null) {

                return false;

            }

  

            // Проверить, если следующий уже

            // указывая на темп

            if (head.next == temp) {

                return true;

            }

  

            // Сохраняем указатель на следующий узел

            // чтобы перейти к следующему шагу

            Node nex = head.next;

  

            // Сделать следующую точку для температуры

            head.next = temp;

  

            // Получить к следующему узлу в списке

            head = nex;

        }

  

        return false;

    }

  

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

    public static void Main(String[] args)

    {

        Node head = newNode(1);

        head.next = newNode(2);

        head.next.next = newNode(3);

        head.next.next.next = newNode(4);

        head.next.next.next.next = newNode(5);

  

        // Создать цикл для тестирования (5 указывает на 3) /

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

  

        Boolean found = detectLoop(head);

        if (found)

            Console.WriteLine("Loop Found");

        else

            Console.WriteLine("No Loop");

    }

}

  
// Этот код предоставлен Принчи Сингхом

Выход:

Loop Found

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Определить петлю в связанном списке

0.00 (0%) 0 votes