Dada una lista enlazada, compruebe si la lista enlazada tiene un bucle o no. El siguiente diagrama muestra una lista enlazada con un bucle.
C++
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node;
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
unordered_set<Node*> s;
while (h != NULL) {
// If this node is already present
// in hashmap it means there is a cycle
// (Because you will be encountering the
// node for the second time).
if (s.find(h) != s.end())
return true;
// If we are seeing the node for
// the first time, insert it in hash
s.insert(h);
h = h->next;
}
return false;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
// This code is contributed by Geetanjali
Java
// Java program to detect loop in a linked list
import java.util.*;
public class LinkedList {
static Node head; // head of list
/* Linked list Node*/
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Inserts a new Node at front of the list. */
static public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Returns true if there is a loop in linked
// list else returns false.
static boolean detectLoop(Node h)
{
HashSet<Node> s = new HashSet<Node>();
while (h != null) {
// If we have already has this node
// in hashmap it means their is a cycle
// (Because you we encountering the
// node second time).
if (s.contains(h))
return true;
// If we are seeing the node for
// the first time, insert it in hash
s.add(h);
h = h.next;
}
return false;
}
/* Driver program to test above function */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(10);
/*Create loop for testing */
llist.head.next.next.next.next = llist.head;
if (detectLoop(head))
System.out.println("Loop found");
else
System.out.println("No Loop");
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to detect loop
# in the linked list
# Node class
class Node:
# Constructor to initialize
# the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new
# node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to print it
# the linked 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):
# If we have already has
# this node in hashmap it
# means their is a cycle
# (Because you we encountering
# the node second time).
if (temp in s):
return True
# If we are seeing the node for
# the first time, insert it in hash
s.add(temp)
temp = temp.next
return False
# Driver program for testing
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)
# Create a loop for testing
llist.head.next.next.next.next = llist.head
if(llist.detectLoop()):
print("Loop found")
else:
print("No Loop ")
# This code is contributed by Gitanjali.
C#
// C# program to detect loop in a linked list
using System;
using System.Collections.Generic;
class LinkedList {
// head of list
public Node head;
/* Linked list Node*/
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Returns true if there is a loop in linked
// list else returns false.
public static bool detectLoop(Node h)
{
HashSet<Node> s = new HashSet<Node>();
while (h != null) {
// If we have already has this node
// in hashmap it means their is a cycle
// (Because you we encountering the
// node second time).
if (s.Contains(h))
return true;
// If we are seeing the node for
// the first time, insert it in hash
s.Add(h);
h = h.next;
}
return false;
}
/* Driver code*/
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(10);
/*Create loop for testing */
llist.head.next.next.next.next = llist.head;
if (detectLoop(llist.head))
Console.WriteLine("Loop found");
else
Console.WriteLine("No Loop");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to detect loop in a linked list
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Returns true if there is a loop in linked
// list else returns false.
function detectLoop(h) {
var s = new Set();
while (h != null) {
// If we have already has this node
// in hashmap it means their is a cycle
// (Because you we encountering the
// node second time).
if (s.has(h))
return true;
// If we are seeing the node for
// the first time, insert it in hash
s.add(h);
h = h.next;
}
return false;
}
/* Driver program to test above function */
push(20);
push(4);
push(15);
push(10);
/* Create loop for testing */
head.next.next.next.next = head;
if (detectLoop(head))
document.write("Loop found");
else
document.write("No Loop");
// This code is contributed by todaysgaurav
</script>
C++
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
int flag;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node;
/* put in the data */
new_node->data = new_data;
new_node->flag = 0;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
while (h != NULL) {
// If this node is already traverse
// it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (h->flag == 1)
return true;
// If we are seeing the node for
// the first time, mark its flag as 1
h->flag = 1;
h = h->next;
}
return false;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
// This code is contributed by Geetanjali
C
// C program to detect loop in a linked list
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
int flag;
} Node;
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (Node*)malloc(sizeof(Node));
/* put in the data */
new_node->data = new_data;
new_node->flag = 0;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
while (h != NULL) {
// If this node is already traverse
// it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (h->flag == 1)
return true;
// If we are seeing the node for
// the first time, mark its flag as 1
h->flag = 1;
h = h->next;
}
return false;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
printf("Loop found");
else
printf("No Loop");
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to detect loop in a linked list
import java.util.*;
class GFG{
// Link list node
static class Node
{
int data;
Node next;
int flag;
};
static Node push(Node head_ref, int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
new_node.flag = 0;
// Link the old list off the new node
new_node.next = head_ref;
// Move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Returns true if there is a loop in linked
// list else returns false.
static boolean detectLoop(Node h)
{
while (h != null)
{
// If this node is already traverse
// it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (h.flag == 1)
return true;
// If we are seeing the node for
// the first time, mark its flag as 1
h.flag = 1;
h = h.next;
}
return false;
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
Node head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 15);
head = push(head, 10);
// Create a loop for testing
head.next.next.next.next = head;
if (detectLoop(head))
System.out.print("Loop found");
else
System.out.print("No Loop");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to detect loop in a linked list
''' Link list node '''
class Node:
def __init__(self):
self.data = 0
self.next = None
self.flag = 0
def push(head_ref, new_data):
''' allocate node '''
new_node = Node();
''' put in the data '''
new_node.data = new_data;
new_node.flag = 0;
''' link the old list off the new node '''
new_node.next = (head_ref);
''' move the head to point to the new node '''
(head_ref) = new_node;
return head_ref
# Returns true if there is a loop in linked list
# else returns false.
def detectLoop(h):
while (h != None):
# If this node is already traverse
# it means there is a cycle
# (Because you we encountering the
# node for the second time).
if (h.flag == 1):
return True;
# If we are seeing the node for
# the first time, mark its flag as 1
h.flag = 1;
h = h.next;
return False;
''' Driver program to test above function'''
if __name__=='__main__':
''' Start with the empty list '''
head = None;
head = push(head, 20);
head = push(head, 4);
head = push(head, 15);
head = push( head, 10)
''' Create a loop for testing '''
head.next.next.next.next = head;
if (detectLoop(head)):
print("Loop found")
else:
print("No Loop")
# This code is contributed by rutvik_56
C#
// C# program to detect loop in a linked list
using System;
class GFG{
// Link list node
class Node
{
public int data;
public Node next;
public int flag;
};
static Node push(Node head_ref, int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
new_node.flag = 0;
// Link the old list off the new node
new_node.next = head_ref;
// Move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Returns true if there is a loop in linked
// list else returns false.
static bool detectLoop(Node h)
{
while (h != null)
{
// If this node is already traverse
// it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (h.flag == 1)
return true;
// If we are seeing the node for
// the first time, mark its flag as 1
h.flag = 1;
h = h.next;
}
return false;
}
// Driver code
public static void Main(string[] args)
{
// Start with the empty list
Node head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 15);
head = push(head, 10);
// Create a loop for testing
head.next.next.next.next = head;
if (detectLoop(head))
Console.Write("Loop found");
else
Console.Write("No Loop");
}
}
// This code is contributed by pratham76
Javascript
<script>
// JavaScript program to detect loop in a linked list
// Link list node
class Node
{
constructor()
{
let data;
let next;
let flag;
}
}
function push( head_ref, new_data)
{
// Allocate node
let new_node = new Node();
// Put in the data
new_node.data = new_data;
new_node.flag = 0;
// Link the old list off the new node
new_node.next = head_ref;
// Move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Returns true if there is a loop in linked
// list else returns false.
function detectLoop(h)
{
while (h != null)
{
// If this node is already traverse
// it means there is a cycle
// (Because you we encountering the
// node for the second time).
if (h.flag == 1)
return true;
// If we are seeing the node for
// the first time, mark its flag as 1
h.flag = 1;
h = h.next;
}
return false;
}
// Driver code
// Start with the empty list
let head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 15);
head = push(head, 10);
// Create a loop for testing
head.next.next.next.next = head;
if (detectLoop(head))
document.write("Loop found");
else
document.write("No Loop");
// This code is contributed by rag2127
</script>
C++
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*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) {
return 1;
}
}
return 0;
}
/* Driver code*/
int main()
{
/* Start with the empty list */
Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}
// This is code is contributed by rathbhupendra
C
// C program to detect loop in a linked list
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*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) {
return 1;
}
}
return 0;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
/* Create a loop for testing */
head->next->next->next->next = head;
if (detectLoop(head))
printf("Loop found");
else
printf("No Loop");
return 0;
}
Java
// Java program to detect loop in a linked list
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
void detectLoop()
{
Node slow_p = head, fast_p = head;
int flag = 0;
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) {
flag = 1;
break;
}
}
if (flag == 1)
System.out.println("Loop found");
else
System.out.println("Loop not found");
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(10);
/*Create loop for testing */
llist.head.next.next.next.next = llist.head;
llist.detectLoop();
}
}
/* This code is contributed by Rajat Mishra. */
Python
# Python program to detect loop in the linked list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print it the linked 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: return 1 return 0 # Driver program for testing llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(10) # Create a loop for testing llist.head.next.next.next.next = llist.head if(llist.detectLoop()): print "Found Loop" else: print "No Loop" # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to detect loop in a linked list
using System;
public class LinkedList {
Node head; // head of list
/* Linked list Node*/
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
Boolean 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) {
return true;
}
}
return false;
}
/* Driver code */
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(10);
/*Create loop for testing */
llist.head.next.next.next.next = llist.head;
Boolean found = llist.detectLoop();
if (found) {
Console.WriteLine("Loop Found");
}
else {
Console.WriteLine("No Loop");
}
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to detect loop in a linked list
let head; // head of list
/* Linked list Node*/
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
/* Inserts a new Node at front of the list. */
function push(new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
let new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
function detectLoop()
{
let slow_p = head, fast_p = head;
let flag = 0;
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)
{
flag = 1;
break;
}
}
if (flag == 1)
document.write("Loop found<br>");
else
document.write("Loop not found<br>");
}
// Driver code
push(20);
push(4);
push(15);
push(10);
// Create loop for testing
head.next.next.next.next = head;
detectLoop();
// This code is contributed by avanitrachhadiya2155
</script>
C++
// C++ program to return first node of loop
#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;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// Create a temporary node
Node* temp = new Node;
while (head != NULL) {
// This condition is for the case when there is no loop
if (head->next == NULL)
return false;
// Check if next is already pointing to temp
if (head->next == temp)
return true;
// Store the pointer to the next node
// in order to get to it in the next step
Node* next = head->next;
// Make next point to temp
head->next = temp;
// Get to the next node in the list
head = next;
}
return false;
}
/* Driver program to test above function*/
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);
/* Create a loop for testing(5 is pointing to 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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C++ program to return first node of loop
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* next;
} Node;
Node* newNode(int key)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
printf("%d ", head->key);
head = head->next;
}
printf("\n");
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// Create a temporary node
Node* temp = (Node*)malloc(sizeof(Node));
while (head != NULL) {
// This condition is for the case when there is no
// loop
if (head->next == NULL)
return false;
// Check if next is already pointing to temp
if (head->next == temp)
return true;
// Store the pointer to the next node
// in order to get to it in the next step
Node* next = head->next;
// Make next point to temp
head->next = temp;
// Get to the next node in the list
head = next;
}
return false;
}
/* Driver program to test above function*/
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);
/* Create a loop for testing(5 is pointing to 3) */
head->next->next->next->next->next = head->next->next;
bool found = detectLoop(head);
if (found)
printf("Loop Found");
else
printf("No Loop");
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to return first node of loop
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;
}
// A utility function to print a linked list
static void printList(Node head)
{
while (head != null) {
System.out.print(head.key + " ");
head = head.next;
}
System.out.println();
}
// Function to detect first node of loop
// in a linked list that may contain loop
static boolean detectLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
while (head != null) {
// This condition is for the case
// when there is no loop
if (head.next == null) {
return false;
}
// Check if next is already
// pointing to temp
if (head.next == temp) {
return true;
}
// Store the pointer to the next node
// in order to get to it in the next step
Node next = head.next;
// Make next point to temp
head.next = temp;
// Get to the next node in the list
head = nex;
}
return false;
}
// Driver code
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);
// Create a loop for testing(5 is pointing to 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");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to return first node of loop
# A binary tree node has data, pointer to
# left child and a pointer to right child
# Helper function that allocates a new node
# with the given data and None left and
# right pointers
class newNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# A utility function to print a linked list
def printList(head):
while (head != None):
print(head.key, end=" ")
head = head.next
print()
# Function to detect first node of loop
# in a linked list that may contain loop
def detectLoop(head):
# Create a temporary node
temp = ""
while (head != None):
# This condition is for the case
# when there is no loop
if (head.next == None):
return False
# Check if next is already
# pointing to temp
if (head.next == temp):
return True
# Store the pointer to the next node
# in order to get to it in the next step
next = head.next
# Make next point to temp
head.next = temp
# Get to the next node in the list
head = nex
return False
# Driver Code
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)
# Create a loop for testing(5 is pointing to 3)
head.next.next.next.next.next = head.next.next
found = detectLoop(head)
if (found):
print("Loop Found")
else:
print("No Loop")
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to return first node of loop
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;
}
// A utility function to print a linked list
static void printList(Node head)
{
while (head != null) {
Console.Write(head.key + " ");
head = head.next;
}
Console.WriteLine();
}
// Function to detect first node of loop
// in a linked list that may contain loop
static Boolean detectLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
while (head != null) {
// This condition is for the case
// when there is no loop
if (head.next == null) {
return false;
}
// Check if next is already
// pointing to temp
if (head.next == temp) {
return true;
}
// Store the pointer to the next node
// in order to get to it in the next step
Node next = head.next;
// Make next point to temp
head.next = temp;
// Get to the next node in the list
head = nex;
}
return false;
}
// Driver code
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);
// Create a loop for testing(5 is pointing to 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");
}
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to return first node of loop
class Node
{
constructor(key)
{
this.key = key;
this.next = null;
}
}
// A utility function to print a linked list
function printList(head)
{
while (head != null)
{
document.write(head.key + " ");
head = head.next;
}
document.write("<br>");
}
// Function to detect first node of loop
// in a linked list that may contain loop
function detectLoop(head)
{
// Create a temporary node
let temp = new Node();
while (head != null)
{
// This condition is for the case
// when there is no loop
if (head.next == null)
{
return false;
}
// Check if next is already
// pointing to temp
if (head.next == temp)
{
return true;
}
// Store the pointer to the next node
// in order to get to it in the next step
let next = head.next;
// Make next point to temp
head.next = temp;
// Get to the next node in the list
head = nex;
}
return false;
}
// Driver code
let 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(5 is pointing to 3) /
head.next.next.next.next.next = head.next.next;
let found = detectLoop(head);
if (found)
document.write("Loop Found");
else
document.write("No Loop");
// This code is contributed by ab2127
</script>
C++
// C++ program to return first node of loop
#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;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
/*returns distance between first and last node every time
* last node moves forwards*/
int distance(Node* first, Node* last)
{
/*counts no of nodes between first and last*/
int counter = 0;
Node* curr;
curr = first;
while (curr != last) {
counter += 1;
curr = curr->next;
}
return counter + 1;
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// Create a temporary node
Node* temp = new Node;
Node *first, *last;
/*first always points to head*/
first = head;
/*last pointer initially points to head*/
last = head;
/*current_length stores no of nodes between current
* position of first and last*/
int current_length = 0;
/*prev_length stores no of nodes between previous
* position of first and last*/
int prev_length = -1;
while (current_length > prev_length && last != NULL) {
// set prev_length to current length then update the
// current length
prev_length = current_length;
// distance is calculated
current_length = distance(first, last);
// last node points the next node
last = last->next;
}
if (last == NULL) {
return false;
}
else {
return true;
}
}
/* Driver program to test above function*/
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);
/* Create a loop for testing(5 is pointing to 3) */
head->next->next->next->next->next = head->next->next;
bool found = detectLoop(head);
if (found)
cout << "Loop Found";
else
cout << "No Loop Found";
return 0;
}
Java
// Java program to return first node of loop
import java.util.*;
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;
}
// A utility function to print a linked list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.key + " ");
head = head.next;
}
System.out.println();
}
/*returns distance between first and last node every time
* last node moves forwards*/
static int distance(Node first, Node last)
{
/*counts no of nodes between first and last*/
int counter = 0;
Node curr;
curr = first;
while (curr != last)
{
counter += 1;
curr = curr.next;
}
return counter + 1;
}
// Function to detect first node of loop
// in a linked list that may contain loop
static boolean detectLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
Node first, last;
/*first always points to head*/
first = head;
/*last pointer initially points to head*/
last = head;
/*current_length stores no of nodes between current
* position of first and last*/
int current_length = 0;
/*current_length stores no of nodes between previous
* position of first and last*/
int prev_length = -1;
while (current_length > prev_length && last != null)
{
// set prev_length to current length then update the
// current length
prev_length = current_length;
// distance is calculated
current_length = distance(first, last);
// last node points the next node
last = last.next;
}
if (last == null)
{
return false;
}
else
{
return true;
}
}
/* Driver program to test above function*/
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);
/* Create a loop for testing(5 is pointing to 3) */
head.next.next.next.next.next = head.next.next;
boolean found = detectLoop(head);
if (found)
System.out.print("Loop Found");
else
System.out.print("No Loop Found");
}
}
// This code is contributed by gauravrajput1
Python3
# Python program to return first node of loop
class newNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# A utility function to print a linked list
def printList(head):
while (head != None) :
print(head.key, end=" ")
head = head.next;
print()
# returns distance between first and last node every time
# last node moves forwards
def distance(first, last):
# counts no of nodes between first and last
counter = 0
curr = first
while (curr != last):
counter = counter + 1
curr = curr.next
return counter + 1
# Function to detect first node of loop
# in a linked list that may contain loop
def detectLoop(head):
# Create a temporary node
temp = ""
# first always points to head
first = head;
# last pointer initially points to head
last = head;
# current_length stores no of nodes between current
# position of first and last
current_length = 0
#current_length stores no of nodes between previous
# position of first and last*/
prev_length = -1
while (current_length > prev_length and last != None) :
# set prev_length to current length then update the
# current length
prev_length = current_length
# distance is calculated
current_length = distance(first, last)
# last node points the next node
last = last.next;
if (last == None) :
return False
else :
return True
# Driver program to test above function
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);
# Create a loop for testing(5 is pointing to 3)
head.next.next.next.next.next = head.next.next;
found = detectLoop(head)
if (found) :
print("Loop Found")
else :
print("No Loop Found")
# This code is contributed by ihritik
C#
// C# program to return first node of loop
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;
}
// A utility function to print a linked list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.key + " ");
head = head.next;
}
Console.WriteLine();
}
/*returns distance between first and last node every time
* last node moves forwards*/
static int distance(Node first, Node last)
{
/*counts no of nodes between first and last*/
int counter = 0;
Node curr;
curr = first;
while (curr != last)
{
counter += 1;
curr = curr.next;
}
return counter + 1;
}
// Function to detect first node of loop
// in a linked list that may contain loop
static bool detectLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
Node first, last;
/*first always points to head*/
first = head;
/*last pointer initially points to head*/
last = head;
/*current_length stores no of nodes between current
* position of first and last*/
int current_length = 0;
/*current_length stores no of nodes between previous
* position of first and last*/
int prev_length = -1;
while (current_length > prev_length && last != null)
{
// set prev_length to current length then update the
// current length
prev_length = current_length;
// distance is calculated
current_length = distance(first, last);
// last node points the next node
last = last.next;
}
if (last == null)
{
return false;
}
else
{
return true;
}
}
/* Driver program to test above function*/
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);
/* Create a loop for testing(5 is pointing to 3) */
head.next.next.next.next.next = head.next.next;
bool found = detectLoop(head);
if (found)
Console.Write("Loop Found");
else
Console.Write("No Loop Found");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to return first node of loop
class Node
{
constructor(key)
{
this.key = key;
this.next = null;
}
}
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// A utility function to print a linked list
function printList(head)
{
while (head != null)
{
document.write(head.key + " ");
head = head.next;
}
document.write("</br>");
}
/*returns distance between first and last
node every time last node moves forwards*/
function distance(first, last)
{
/*counts no of nodes between first and last*/
let counter = 0;
let curr;
curr = first;
while (curr != last)
{
counter += 1;
curr = curr.next;
}
return counter + 1;
}
// Function to detect first node of loop
// in a linked list that may contain loop
function detectLoop(head)
{
// Create a temporary node
let temp = new Node();
let first, last;
/*first always points to head*/
first = head;
/*last pointer initially points to head*/
last = head;
/*current_length stores no of nodes
between current position of first and last*/
let current_length = 0;
/*current_length stores no of nodes between
previous position of first and last*/
let prev_length = -1;
while (current_length > prev_length &&
last != null)
{
// Set prev_length to current length
// then update the current length
prev_length = current_length;
// Distance is calculated
current_length = distance(first, last);
// Last node points the next node
last = last.next;
}
if (last == null)
{
return false;
}
else
{
return true;
}
}
// Driver code
let 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);
/* Create a loop for testing(5 is pointing to 3) */
head.next.next.next.next.next = head.next.next;
let found = detectLoop(head);
if (found)
document.write("Loop Found");
else
document.write("No Loop Found");
// This code is contributed by divyeshrabadiya07
</script>
C++
// C++ program to return first node of loop
#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;
}
// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
// If the head is null we will return false
if (!head)
return 0;
else {
// Traversing the linked list
// for detecting loop
while (head) {
// If loop found
if (head->key == -1) {
return true;
}
// Changing the data of visited node to any
// value which is outside th given range here it
// is supposed the given range is (1 <= Data on
// Node <= 10^3)
else {
head->key = -1;
head = head->next;
}
}
// If loop not found return false
return 0;
}
}
/* Driver program to test above function*/
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);
/* Create a loop for testing(5 is pointing to 3) */
head->next->next->next->next->next = head->next->next;
bool found = detectLoop(head);
cout << found << endl;
return 0;
}
Java
// Java program to return first node of loop
import java.util.*;
class LinkedList{
// Head of list
static Node head;
// Linked list Node
static class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Inserts a new Node at front of the list. */
static public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Function to detect first node of loop
// in a linked list that may contain loop
static boolean detectLoop(Node h)
{
// If the head is null we will return false
if (head == null)
return false;
else
{
// Traversing the linked list
// for detecting loop
while (head != null)
{
// If loop found
if (head.data == -1)
{
return true;
}
// Changing the data of visited node to any
// value which is outside th given range
// here it is supposed the given range is (1
// <= Data on Node <= 10^3)
else
{
head.data = -1;
head = head.next;
}
}
// If loop not found return false
return false;
}
}
// Driver Code
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(1);
llist.push(2);
llist.push(3);
llist.push(4);
llist.push(5);
/* Create a loop for testing */
llist.head.next.next.next.next.next = llist.head.next.next;
if (detectLoop(llist.head))
System.out.println("1");
else
System.out.println("0");
}
}
// This code is contributed by RohitOberoi
Python3
# Python program to return first node of loop
class Node:
def __init__(self,d):
self.data = d
self.next = None
head = None
def push(new_data):
global head
new_node = Node(new_data)
new_node.next = head
head=new_node
def detectLoop(h):
global head
if (head == None):
return False
else:
while (head != None):
if (head.data == -1):
return True
else:
head.data = -1
head = head.next
return False
push(1);
push(2);
push(3);
push(4);
push(5);
head.next.next.next.next.next = head.next.next
if (detectLoop(head)):
print("1")
else:
print("0")
# This code is contributed by patel2127.
C#
// C# program to return first node of loop
using System;
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
public class GFG{
// Head of list
static Node head;
/* Inserts a new Node at front of the list. */
static public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Function to detect first node of loop
// in a linked list that may contain loop
static bool detectLoop(Node h)
{
// If the head is null we will return false
if (head == null)
return false;
else
{
// Traversing the linked list
// for detecting loop
while (head != null)
{
// If loop found
if (head.data == -1)
{
return true;
}
// Changing the data of visited node to any
// value which is outside th given range
// here it is supposed the given range is (1
// <= Data on Node <= 10^3)
else
{
head.data = -1;
head = head.next;
}
}
// If loop not found return false
return false;
}
}
// Driver Code
static public void Main (){
push(1);
push(2);
push(3);
push(4);
push(5);
/* Create a loop for testing */
head.next.next.next.next.next = head.next.next;
if (detectLoop(head))
Console.WriteLine("1");
else
Console.WriteLine("0");
}
}
Javascript
<script>
// Javascript program to return first node of loop
// Linked list Node
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
// Head of list
let head;
/* Inserts a new Node at front of the list. */
function push(new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
let new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
// Function to detect first node of loop
// in a linked list that may contain loop
function detectLoop(h)
{
// If the head is null we will return false
if (head == null)
return false;
else
{
// Traversing the linked list
// for detecting loop
while (head != null)
{
// If loop found
if (head.data == -1)
{
return true;
}
// Changing the data of visited node to any
// value which is outside th given range
// here it is supposed the given range is (1
// <= Data on Node <= 10^3)
else
{
head.data = -1;
head = head.next;
}
}
// If loop not found return false
return false;
}
}
// Driver Code
push(1);
push(2);
push(3);
push(4);
push(5);
/* Create a loop for testing */
head.next.next.next.next.next = head.next.next;
if (detectLoop(head))
document.write("1");
else
document.write("0");
// This code is contributed by unknown2108
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA