Escriba un programa que compruebe si una lista enlazada determinada contiene un bucle y, si hay un bucle presente, devuelve el recuento de Nodes en el bucle. Por ejemplo, un bucle está presente en la lista de enlaces a continuación y la longitud del bucle es 4. Si el bucle no está presente, la función debería devolver 0.
Enfoque: En esta publicación, usaremos el concepto de Mapa para almacenar las direcciones de los Nodes presentes en la lista vinculada como una clave y su posición como los valores.
A continuación se muestra el enfoque paso a paso:
- Atraviese cada Node de la lista enlazada y mantenga la posición a partir de uno. Incrementa la posición después de cada Node.
- Compruebe si ese Node está presente en el Mapa o no.
- Si el mapa no contiene la dirección de ese Node, insértelo en el mapa junto con su posición.
- Si el mapa ya contiene la dirección de ese Node, devuelve la diferencia entre sus posiciones.
- Si no se ha encontrado dicho Node, devuelva 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find length of loop
// in a linked list using Map
#include <bits/stdc++.h>
using namespace std;
// Linked List node
struct Node {
int data;
struct Node* next;
Node(int num)
{
data = num;
next = NULL;
}
};
// Function detects and counts loop
// nodes in the list. If loop is not there,
// then returns 0
int countNodesinLoop(struct Node* head)
{
struct Node* p = head;
int pos = 0;
// Maintain a map to store addresses
// of node and their position
unordered_map<Node*, int> m;
// Traverse through the linked list
while (p != NULL) {
// If the node is not present in the map
if (m.find(p) == m.end()) {
m[p] = pos;
pos++;
}
// if the node is present
else {
// Return difference between
// position of the present node and
// position where that node occurred before
return (pos - m[p]);
}
p = p->next;
}
// Return 0 to indicate
// there is no loop
return 0;
}
// Driver code
int main()
{
// Create nodes of the linked list
struct Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
// Create a loop for testing the function
head->next->next->next->next->next = head->next;
// Call the function for the above linked list
cout << countNodesinLoop(head) << endl;
return 0;
}
Java
// Java program to find length of loop
// in a linked list using Map
import java.util.*;
import java.io.*;
class GFG{
static class Node
{
int data;
Node next;
// Constructor
Node(int num)
{
data = num;
next = null;
}
}
// Function detects and counts loop
// nodes in the list. If loop is not there,
// then returns 0
public static int countNodesinLoop(Node head)
{
Node p = head;
int pos = 0;
// Maintain a map to store addresses
// of node and their position
HashMap<Node,
Integer> m = new HashMap<Node,
Integer>();
// Traverse through the linked list
while (p != null)
{
// If the node is not present in the map
if (!m.containsKey(p))
{
m.put(p, pos);
pos++;
}
// If the node is present
else
{
// Return difference between
// position of the present
// node and position where
// that node occurred before
return (pos - m.get(p));
}
p = p.next;
}
// Return 0 to indicate
// there is no loop
return 0;
}
// Driver code
public static void main (String[] args)
{
// Create nodes of the linked list
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Create a loop for testing the function
head.next.next.next.next.next = head.next;
// Call the function for the above linked list
System.out.println(countNodesinLoop(head));
}
}
// This code is contributed by adityapande88
Python3
# Python3 program to find length of loop # in a linked list using Map # Linked List node class Node: def __init__(self, data): self.data = data self.next = None # Function detects and counts loop # nodes in the list. If loop is not there, # then returns 0 def countNodesinLoop(head): p = head; pos = 0; # Maintain a map to store addresses # of node and their position m = dict() # Traverse through the linked list while (p != None): # If the node is not present in the map if (p not in m): m[p] = pos; pos += 1 # if the node is present else: # Return difference between # position of the present node and # position where that node occurred before return (pos - m[p]); p = p.next; # Return 0 to indicate # there is no loop return 0; # Driver code if __name__=='__main__': # Create nodes of the linked list head = Node(1); head.next = Node(2); head.next.next = Node(3); head.next.next.next = Node(4); head.next.next.next.next = Node(5); # Create a loop for testing the function head.next.next.next.next.next = head.next; # Call the function for the above linked list print(countNodesinLoop(head)) # This code is contributed by Pratham76
C#
// C# program to find length of loop
// in a linked list using Map
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
public class Node
{
public int data;
public Node next;
// Constructor
public Node(int num)
{
data = num;
next = null;
}
}
// Function detects and counts loop
// nodes in the list. If loop is not there,
// then returns 0
public static int countNodesinLoop(Node head)
{
Node p = head;
int pos = 0;
// Maintain a map to store addresses
// of node and their position
Dictionary<Node,
int> m = new Dictionary<Node,
int>();
// Traverse through the linked list
while (p != null)
{
// If the node is not present in the map
if (!m.ContainsKey(p))
{
m[p] = pos;
pos++;
}
// If the node is present
else
{
// Return difference between
// position of the present
// node and position where
// that node occurred before
return (pos - m[p]);
}
p = p.next;
}
// Return 0 to indicate
// there is no loop
return 0;
}
// Driver code
public static void Main(string[] args)
{
// Create nodes of the linked list
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Create a loop for testing the function
head.next.next.next.next.next = head.next;
// Call the function for the above linked list
Console.Write(countNodesinLoop(head));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find length of loop
// in a linked list using Map
// Linked List node
class Node {
constructor(num)
{
this.data = num;
this.next = null;
}
};
// Function detects and counts loop
// nodes in the list. If loop is not there,
// then returns 0
function countNodesinLoop(head)
{
var p = head;
var pos = 0;
// Maintain a map to store addresses
// of node and their position
var m = new Map();
// Traverse through the linked list
while (p != null) {
// If the node is not present in the map
if (!m.has(p)) {
m.set(p, pos);
pos++;
}
// if the node is present
else {
// Return difference between
// position of the present node and
// position where that node occurred before
return (pos - m.get(p));
}
p = p.next;
}
// Return 0 to indicate
// there is no loop
return 0;
}
// Driver code
// Create nodes of the linked list
var head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Create a loop for testing the function
head.next.next.next.next.next = head.next;
// Call the function for the above linked list
document.write( countNodesinLoop(head));
// This code is contributed by noob2000.
</script>
Producción
4
Artículo similar: encuentre la longitud de un bucle en una lista vinculada utilizando el algoritmo de detección de ciclo de Floyd
Publicación traducida automáticamente
Artículo escrito por tapassaha699 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA