# 算法题：如何检测检测链表中的循环？

2021年3月25日11:50:45 发表评论 901 次浏览

## 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 */

/* move the head to point to the 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 we 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;

/* Create a loop for testing */

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

/* 4. Move the head to point to 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

h = h.next;
}

return false ;
}

/* Driver program to test above function */
public static void main(String[] args)
{

llist.push( 20 );
llist.push( 4 );
llist.push( 15 );
llist.push( 10 );

/*Create loop for testing */

System.out.println( "Loop found" );
else
System.out.println( "No Loop" );
}
}

// This code is contributed by Arnav Kr. Mandal.``````

## Python3

``````# 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

# 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
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

temp = temp. next

return False

# Driver program for testing
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;

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

/* 4. Move the head to point to 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

h = h.next;
}

return false ;
}

/* Driver code*/
public static void Main(String[] args)
{

llist.push(20);
llist.push(4);
llist.push(15);
llist.push(10);

/*Create loop for testing */

Console.WriteLine( "Loop found" );
else
Console.WriteLine( "No Loop" );
}
}

// This code has been contributed by 29AjayKumar``````

``Loop found``

• 时间复杂度：O(n)。
只需循环一次即可。
• 辅助空间：O(n)。
n是将值存储在哈希图中所需的空间。

:

• 每个节点都有一个访问标志。
• 遍历链接列表并继续标记访问的节点。
• 如果你再次看到一个访问过的节点, 那么就会有一个循环。该解决方案适用于O(n), 但每个节点都需要其他信息。
• 此解决方案的一种变体不需要修改基本数据结构, 可以使用哈希来实现, 只需将访问的节点的地址存储在哈希中即可, 如果你看到哈希中已存在的地址, 则会出现循环。

## CPP14

``````// 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 */

/* move the head to point to the 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;

/* Create a loop for testing */

cout << "Loop found" ;
else
cout << "No Loop" ;

return 0;
}
// This code is contributed by Geetanjali``````

``Loop Found``

• 时间复杂度：上)。
只需循环一次即可。
• 辅助空间：上)。
n是将值存储在哈希图中所需的空间。

：弗洛伊德(Floyd)的循环查找算法

• 使用两个指针遍历链表。
• 将一个指针(slow_p)移动一个, 将另一个指针(fast_p)移动两个。
• 如果这些指针在同一节点相遇, 则存在循环。如果指针不符合要求, 则链接列表没有循环。

Floyd的循环查找算法的实现：

## 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 */

/* move the head to point to the 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;

/* Create a loop for testing */
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 */

/* move the head to point to the 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;

/* Create a loop for testing */

printf ( "Loop found" );
else
printf ( "No Loop" );
return 0;
}``````

## Java

``````// Java program to detect loop in a linked 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 */

/* 4. Move the head to point to 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
}

/* Driver program to test above functions */
public static void main(String args[])
{

llist.push( 20 );
llist.push( 4 );
llist.push( 15 );
llist.push( 10 );

/*Create loop for testing */

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

# 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

# Driver program for testing
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 {

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

/* 4. Move the head to point to 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)
{

llist.push(20);
llist.push(4);
llist.push(15);
llist.push(10);
/*Create loop for testing */

Boolean found = llist.detectLoop();
if (found) {
Console.WriteLine( "Loop Found" );
}
else {
Console.WriteLine( "No Loop" );
}
}
}

// This code is contributed by Princi Singh``````

``Found Loop``

• 时间复杂度：O(n)。
只需循环一次即可。
• 辅助空间：O(1)。
不需要空间。

Floyd的慢速指针和快速指针方法如何工作？

http://en.wikipedia.org/wiki/Cycle_detection

：标记访问的节点而不修改链接列表数据结构

## 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
{
while (head != NULL) {
cout << head->key << " " ;
}
cout << endl;
}

// Function to detect first node of loop
// in a linked list that may contain loop
{

// 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* nex = head->next;

// Make next point to temp

// Get to the next node in the list
}

return false ;
}

/* Driver program to test above function*/
int main()
{
Node* head = newNode(1);

/* Create a loop for testing(5 is pointing to 3) */

bool found = detectLoop(head);
if (found)
cout << "Loop Found" ;
else
cout << "No Loop" ;

return 0;
}``````

## 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 + " " );
}
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 nex = head.next;

// Make next point to temp

// Get to the next node in the list
}

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

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 pra linked list
while (head ! = None ):
print (head.key, end = " " )

print ()

# Function to detect first node of loop
# in a linked list that may contain loop

# 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
nex = head. next

# Make next poto temp
head. next = temp

# Get to the next node in the list

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

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 + " " );
}
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 nex = head.next;

// Make next point to temp

// Get to the next node in the list
}

return false ;
}

// Driver code
public static void Main(String[] args)
{
Node head = newNode(1);

// Create a loop for testing(5 is pointing to 3)

Boolean found = detectLoop(head);
if (found) {
Console.WriteLine( "Loop Found" );
}
else {
Console.WriteLine( "No Loop" );
}
}
}

// This code is contributed by Princi Singh``````

``Loop Found``

• 时间复杂度：O(n)。
只需循环一次即可。
• 辅助空间：O(1)。
不需要空间。

## 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
{
while (head != NULL) {
cout << head->key << " " ;
}
cout << endl;
}

/*returns distance between first and last node every time
* last node moves forwars*/
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
{

// Create a temporary node
Node* temp = new Node;

Node *first, *last;

/*first always points to head*/
/*last pointer initially points to 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*/
int main()
{
Node* head = newNode(1);

/* Create a loop for testing(5 is pointing to 3) */

bool found = detectLoop(head);
if (found)
cout << "Loop Found" ;
else
cout << "No Loop Found" ;

return 0;
}``````

``Loop Found``

• 时间复杂度：O(n^2)
• 辅助空间：O(1)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。