本文概述 给定一个链表, 检查链表是否有循环。下图显示了带有循环的链表。

文章图片
以下是执行此操作的不同方法
解决方案1：
散列
方法：
遍历该列表, 并将节点地址始终放在哈希表中。在任何时候, 如果达到NULL, 则返回false, 如果当前节点的下一个指向Hash中先前存储的任何节点, 则返回true。
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 = https://www.lsbin.com/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 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; 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 = https://www.lsbin.com/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

# 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 = https://www.lsbin.com/data self . next = Noneclass 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. nextdef 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. nextreturn 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 = https://www.lsbin.com/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

输出如下：

Loop found

【算法题（如何检测检测链表中的循环（））】复杂度分析：

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

解决方案2
:
通过修改链接列表数据结构, 无需哈希图即可解决此问题。
方法：
此解决方案需要修改基本的链表数据结构。

• 每个节点都有一个访问标志。
• 遍历链接列表并继续标记访问的节点。
• 如果你再次看到一个访问过的节点, 那么就会有一个循环。该解决方案适用于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 = https://www.lsbin.com/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

输出如下：

Loop Found

复杂度分析：

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

解决方案3
：弗洛伊德(Floyd)的循环查找算法
方法：
这是最快的方法, 下面进行了介绍：

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

下图显示了detectloop函数在代码中的工作方式：

文章图片
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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 = https://www.lsbin.com/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 = https://www.lsbin.com/data self . next = Noneclass 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. nextdef 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 = 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 = https://www.lsbin.com/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

输出如下：

Found Loop

复杂度分析：

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

以上算法如何工作？
请参阅 ：
Floyd的慢速指针和快速指针方法如何工作？
参考文献：
http://en.wikipedia.org/wiki/Cycle_detection
http://ostermiller.org/find_loop_singly_linked_list.html
解决方案4
：标记访问的节点而不修改链接列表数据结构
在这种方法中, 将创建一个临时节点。使遍历的每个节点的下一个指针指向该临时节点。这样, 我们将节点的下一个指针用作标志来指示该节点是否已遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下, 第二次遍历该条件将成立, 因此我们发现该循环存在。如果遇到一个指向null的节点, 则循环不存在。
下面是上述方法的实现：
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* nex = head-> next; // Make next point to temp head-> next = temp; // Get to the next node in the list head = nex; }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; }

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 nex = 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 pra linked list def printList(head): while (head ! = None ): print (head.key, end = " " ) head = head. nextprint ()# 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 nex = head. next# Make next poto temp head. next = temp# Get to the next node in the list head = nexreturn 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 . nextfound = 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 nex = 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

输出如下：

Loop Found

复杂度分析：

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

解决方案5：储存长度
在此方法中, 将创建两个指针, 第一个(始终指向头)和最后一个指针。每次最后一个指针移动时, 我们都会计算第一个和最后一个之间的节点数, 并检查当前节点数是否大于先前的节点数, 如果是, 我们通过移动最后一个指针进行操作, 否则就意味着我们已经到达循环的终点, 因此我们相应地返回输出。
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 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 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*/ 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; }

输出如下

Loop Found

复杂度分析：

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

推荐阅读

• 

  自汗是什么意思 自汗解释
• 

  怎样熬排骨汤又白又浓
• 

  驾驶证年审手续流程是什么
• 

  高手在民间！！！
• 

  华为P40是几W快充（华为P40的快充是多少）
• 

  早起打卡第62天，早饭打卡第8天
• 

  生菜对环境条件的要求 生菜适合的温度和环境
• 

  经常吃猪肝对身体好吗 经常吃猪肝好不好
• 

  cf手游像我这个比较穷的V5买啥好？
• 

  弹弹堂安卓苹果互通吗,弹弹幽灵大冒险:苹果和安卓不完全互通
• 

  除了《恶作剧之吻》,你还记得哪些小时候看的青春偶像剧？
• 

  苦练郭林气功复发 郭林新气功
• 

  爱普生l360打印机废墨收集垫6
• 

  想问一下在京东买手机靠谱吗？
• 

  美股基金有哪些
• 

  redis槽满了会怎么样 redis的插槽不均匀
• 

  银河破裂者最高难度战役模式怎么玩 战役模式通关方法推荐
• 

  vue+echarts实带渐变效果的折线图
• 

  什么是不成对电子数
• 

  为什么热水器只能75度，怎么修复与排查方法？

• C#中的HashSet介绍与用法示例
• 算法题（如何计算矩形中的正方形数（））
• 如何计算从mXn矩阵的左上角到右下角所有可能的路径（）
• jQuery如何使用fadeToggle()方法（代码示例）
• 如何使用CSS创建波浪背景（代码示例）
• 在PHP数组中如何返回两个日期之间的所有日期（）
• TypeScript数字valueOf()方法用法介绍
• JavaScript赋值运算符深入学习指南
• 雨林木风win8纯净版64位安装版最新系统推荐