Рубрики

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

По заданному односвязному списку определите, является ли связанный список круглым или нет. Связанный список называется циклическим, если он не заканчивается NULL и все узлы связаны в форме цикла. Ниже приведен пример кругового связного списка.

Пустой связанный список считается круговым.

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

Идея состоит в том, чтобы сохранить заголовок связанного списка и пройти его. Если мы достигнем NULL, связанный список не будет круговым. Если достигнуть головы снова, связанный список является круглым.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    struct Node* next;

};

  
/ * Эта функция возвращает true, если дана ссылка

   список является круглым, иначе ложным. * /

bool isCircular(struct Node *head)

{

    // Пустой связанный список является круглым

    if (head == NULL)

       return true;

  

    // Следующая глава

    struct Node *node = head->next;

  

    // Этот цикл остановился бы в обоих случаях (1) Если

    // Круговой (2) Не круговой

    while (node != NULL && node != head)

       node = node->next;

  

    // Если цикл остановлен из-за циклического

    // условие

    return (node == head);

}

  
// Сервисная функция для создания нового узла.

Node *newNode(int data)

{

    struct Node *temp = new Node;

    temp->data = data;

    temp->next = NULL;

    return temp;

}

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

int main()

{

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

    struct Node* head = newNode(1);

    head->next = newNode(2);

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

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

  

    isCircular(head)? cout << "Yes\n" :

                      cout << "No\n" ;

  

    // Делаем связанный список круглым

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

  

    isCircular(head)? cout << "Yes\n" :

                      cout << "No\n" ;

  

    return 0;

}

Джава

// Java программа для проверки
// связанный список круговой

import java.util.*;

  

class GFG

{

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

static class Node

{

    int data;

    Node next;

}

  
/ * Эта функция возвращает true, если дана ссылка
список является круглым, иначе ложным. * /

static boolean isCircular( Node head)

{

    // Пустой связанный список является круглым

    if (head == null)

    return true;

  

    // Следующая глава

    Node node = head.next;

  

    // Этот цикл остановился бы в обоих случаях (1) Если

    // Круговой (2) Не круговой

    while (node != null && node != head)

    node = node.next;

  

    // Если цикл остановлен из-за циклического

    // условие

    return (node == head);

}

  
// Сервисная функция для создания нового узла.

static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.next = null;

    return temp;

}

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

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

  

    System.out.print(isCircular(head)? "Yes\n" :

                    "No\n" );

  

    // Делаем связанный список круглым

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

  

    System.out.print(isCircular(head)? "Yes\n" :

                    "No\n" );

  
}
}

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

python3

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

  
# Класс узла

class Node: 

  

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

    def __init__(self, data): 

        self.data = data # Назначить данные

        self.next = None # Инициализировать следующий как ноль

  

  
# Класс связанного списка содержит объект Node

class LinkedList: 

  

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

    def __init__(self): 

        self.head = None

  

def Circular(head):

    if head==None:

        return True

          

    # Следующая голова

    node = head.next

    i = 0

      

    # Этот цикл остановился бы в обоих случаях (1) Если

    # Круговой (2) Не круговой

    while((node is not None) and (node is not head)):

        i = i + 1

        node = node.next

      

    return(node==head)

  

  
# Выполнение кода начинается здесь

if __name__=='__main__':

    llist = LinkedList() 

    llist.head = Node(1)

    second = Node(2)

    third = Node(3

    fourth = Node(4)

      

    llist.head.next = second;

    second.next = third;

    third.next = fourth

      

    if (Circular(llist.head)):

        print('Yes')

    else:

        print('No')

      

    fourth.next = llist.head

      

    if (Circular(llist.head)):

        print('Yes')

    else:

        print('No')

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

C #

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

using System;

public class GFG 

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

public class Node 

    public int data; 

    public Node next; 

  
/ * Эта функция возвращает true, если дана ссылка
список является круглым, иначе ложным. * /

static bool isCircular( Node head) 

    // Пустой связанный список является круглым

    if (head == null

    return true

  

    // Следующая глава

    Node node = head.next; 

  

    // Этот цикл остановился бы в обоих случаях (1) Если

    // Круговой (2) Не круговой

    while (node != null && node != head) 

    node = node.next; 

  

    // Если цикл остановлен из-за циклического

    // условие

    return (node == head); 

  
// Сервисная функция для создания нового узла.

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.next = null

    return temp; 

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

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

  

    Console.Write(isCircular(head)? "Yes\n"

                    "No\n" ); 

  

    // Делаем связанный список круглым

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

  

    Console.Write(isCircular(head)? "Yes\n"

                    "No\n" ); 

  


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


Выход :

No
Yes

Эта статья пополняемые Шивов Гупт. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes