Dada una lista enlazada , compruebe si la lista enlazada tiene un bucle o no.
Aquí se muestran varios métodos: Detectar ciclo en lista enlazada
Ejemplo
Entrada: 20->4->54->6->NULL
Salida: No se detecta bucle.
Explicación:
Mientras recorremos la lista enlazada, llegamos al final de la lista enlazada. Por lo tanto, no hay ningún bucle presente en la lista enlazada.Entrada: 20->4->5->10->20
Salida: Bucle detectado.
Explicación:
al atravesar la lista enlazada, alcanzando el Node con valor 10, se enlaza con el Node principal, que representa un bucle en la lista enlazada. Por lo tanto, un bucle está presente en la lista enlazada.
Acercarse:
- Cree un mapa que almacenará el Node visitado en la lista vinculada .
- Recorra la lista enlazada y haga lo siguiente:
- Compruebe si el Node actual está presente en el mapa o no.
- Si el Node actual no está presente en el mapa , inserte el Node actual en el mapa.
- Si el Node está presente en el mapa, se detecta el bucle en una lista enlazada.
- Si alcanzamos el Node nulo mientras recorremos la lista enlazada , la lista enlazada dada no tiene ningún bucle presente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to detect loop in
// given linked list using map
#include <bits/stdc++.h>
using namespace std;
// Structure for a node in Linked List
struct Node {
int data;
Node* next;
};
// Function to create Linked List
// Node
Node* newNode(int d)
{
Node* temp = new Node;
temp->data = d;
temp->next = NULL;
return temp;
}
// Declaration of Map to keep
// mark of visited Node
map<Node*, bool> vis;
bool flag = 0;
// Function to check cycle in Linked
// List
void check(Node* head)
{
// If head is NULL return ;
if (head == NULL) {
flag = 0;
return;
}
// Mark the incoming Node as
// visited if it is not visited yet
if (!vis[head]) {
vis[head] = true;
check(head->next);
}
// If a visited Node is found
// Update the flag value to 1
// and return ;
else {
flag = 1;
return;
}
}
// Driver Code
int main()
{
// Create a head Node
Node* head = newNode(20);
// Inserting Node in Linked List
head->next = newNode(4);
head->next->next = newNode(5);
head->next->next->next = newNode(10);
// Just to make a cycle
head->next->next->next->next = head;
// Function that detect cycle in
// Linked List
check(head);
// If flag is true, loop is found
if (flag)
cout << "Loop detected.";
// If flag is false, No Loop
// detected
else
cout << "No Loop Found.";
cout << endl;
return 0;
}
Java
// Java program to detect loop in
// given linked list using map
import java.util.*;
class GFG{
// Structure for a node in Linked List
static class Node
{
int data;
Node next;
};
// Function to create Linked List
// Node
static Node newNode(int d)
{
Node temp = new Node();
temp.data = d;
temp.next = null;
return temp;
}
// Declaration of Map to keep
// mark of visited Node
static HashMap<Node, Boolean> vis = new HashMap<>();
static boolean flag = false;
// Function to check cycle in Linked
// List
static void check(Node head)
{
// If head is null return ;
if (head == null)
{
flag = false;
return;
}
// Mark the incoming Node as
// visited if it is not visited yet
if (vis.containsKey(head))
{
vis.put(head, true);
check(head.next);
}
// If a visited Node is found
// Update the flag value to 1
// and return ;
else
{
flag = true;
return;
}
}
// Driver Code
public static void main(String[] args)
{
// Create a head Node
Node head = newNode(20);
// Inserting Node in Linked List
head.next = newNode(4);
head.next.next = newNode(5);
head.next.next.next = newNode(10);
// Just to make a cycle
head.next.next.next.next = head;
// Function that detect cycle in
// Linked List
check(head);
// If flag is true, loop is found
if (flag)
System.out.print("Loop detected.");
// If flag is false, No Loop
// detected
else
System.out.print("No Loop Found.");
System.out.println();
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to detect loop in
# given linked list using map
# Structure for a node in Linked List
class Node:
def __init__(self, val):
self.data = val
self.Next = None
# Function to create Linked List Node
def newNode(d):
temp = Node(d)
return temp
# Declaration of Map to keep
# mark of visited Node
vis = {}
flag = False
# Function to check cycle in Linked
# List
def check(head):
global vis, flag
# If head is null return ;
if head == None:
flag = False
return
# Mark the incoming Node as
# visited if it is not visited yet
if head not in vis:
vis[head] = True
check(head.Next)
# If a visited Node is found
# Update the flag value to 1
# and return ;
else:
flag = True
return
# Create a head Node
head = newNode(20)
# Inserting Node in Linked List
head.Next = newNode(4)
head.Next.Next = newNode(5)
head.Next.Next.Next = newNode(10)
# Just to make a cycle
head.Next.Next.Next.Next = head
# Function that detect cycle in
# Linked List
check(head)
# If flag is true, loop is found
if flag:
print("Loop detected.")
# If flag is false, No Loop
# detected
else:
print("No Loop Found.")
# This code is contributed by suresh07.
C#
// C# program to detect loop in
// given linked list using map
using System;
using System.Collections.Generic;
class GFG{
// Structure for a node in Linked List
public class Node
{
public int data;
public Node next;
};
// Function to create Linked List
// Node
static Node newNode(int d)
{
Node temp = new Node();
temp.data = d;
temp.next = null;
return temp;
}
// Declaration of Map to keep
// mark of visited Node
static Dictionary<Node,
Boolean> vis = new Dictionary<Node,
Boolean>();
static bool flag = false;
// Function to check cycle in Linked
// List
static void check(Node head)
{
// If head is null return ;
if (head == null)
{
flag = false;
return;
}
// Mark the incoming Node as
// visited if it is not visited yet
if (vis.ContainsKey(head))
{
vis.Add(head, true);
check(head.next);
}
// If a visited Node is found
// Update the flag value to 1
// and return ;
else
{
flag = true;
return;
}
}
// Driver Code
public static void Main(String[] args)
{
// Create a head Node
Node head = newNode(20);
// Inserting Node in Linked List
head.next = newNode(4);
head.next.next = newNode(5);
head.next.next.next = newNode(10);
// Just to make a cycle
head.next.next.next.next = head;
// Function that detect cycle in
// Linked List
check(head);
// If flag is true, loop is found
if (flag)
Console.Write("Loop detected.");
// If flag is false, No Loop
// detected
else
Console.Write("No Loop Found.");
Console.WriteLine();
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program to detect loop in
// given linked list using map
// Structure for a node in Linked List
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to create Linked List
// Node
function newNode(d) {
var temp = new Node();
temp.data = d;
temp.next = null;
return temp;
}
// Declaration of Map to keep
// mark of visited Node
var vis = new Map();;
var flag = false;
// Function to check cycle in Linked
// List
function check(head) {
// If head is null return ;
if (head == null) {
flag = false;
return;
}
// Mark the incoming Node as
// visited if it is not visited yet
if (!vis.has(head)) {
vis.set(head, true);
check(head.next);
}
// If a visited Node is found
// Update the flag value to 1
// and return ;
else {
flag = true;
return;
}
}
// Driver Code
// Create a head Node
var head = newNode(20);
// Inserting Node in Linked List
head.next = newNode(4);
head.next.next = newNode(5);
head.next.next.next = newNode(10);
// Just to make a cycle
head.next.next.next.next = head;
// Function that detect cycle in
// Linked List
check(head);
// If flag is true, loop is found
if (flag)
document.write("Loop detected.");
// If flag is false, No Loop
// detected
else
document.write("No Loop Found.");
document.write();
// This code contributed by Rajput-Ji
</script>
Producción:
Loop detected.
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA