写一个函数 findFirstLoopNode（） 检查给定链表是否包含循环。如果存在循环，则它将点返回到循环的第一个节点。否则返回NULL。
null
例子：
Input : Head of below linked list
![图片[1]-查找链表中循环的第一个节点-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/2009/04/Linked-List-Loop.gif)
Output : Pointer to node 2
我们讨论过 弗洛伊德环路检测算法 .以下是查找循环的第一个节点的步骤。 1.如果发现循环，初始化指向头部的慢速指针，让快速指针处于其位置。 2.将慢速和快速指针一次移动一个节点。 3.它们相遇的点是循环的起点。
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 and remove loop // in a linked list that may contain loop Node* detectAndRemoveLoop(Node* head) { // If list is empty or has only one node // without loop if (head == NULL || head->next == NULL) return NULL; Node *slow = head, *fast = head; // Move slow and fast 1 and 2 steps // ahead respectively. slow = slow->next; fast = fast->next->next; // Search for loop using slow and // fast pointers while (fast && fast->next) { if (slow == fast) break ; slow = slow->next; fast = fast->next->next; } // If loop does not exist if (slow != fast) return NULL; // If loop exists. Start slow from // head and fast from meeting point. slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } /* Driver program to test above function*/ int main() { Node* head = newNode(50); head->next = newNode(20); head->next->next = newNode(15); head->next->next->next = newNode(4); head->next->next->next->next = newNode(10); /* Create a loop for testing */ head->next->next->next->next->next = head->next->next; Node* res = detectAndRemoveLoop(head); if (res == NULL) cout << "Loop does not exist" ; else cout << "Loop starting node is " << res->key; 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(); } // Function to detect and remove loop // in a linked list that may contain loop static Node detectAndRemoveLoop(Node head) { // If list is empty or has // only one node without loop if (head == null || head.next == null ) return null ; Node slow = head, fast = head; // Move slow and fast 1 // and 2 steps ahead // respectively. slow = slow.next; fast = fast.next.next; // Search for loop using // slow and fast pointers while (fast != null && fast.next != null ) { if (slow == fast) break ; slow = slow.next; fast = fast.next.next; } // If loop does not exist if (slow != fast) return null ; // If loop exists. Start slow from // head and fast from meeting point. slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } // Driver code public static void main(String[] args) { Node head = newNode( 50 ); head.next = newNode( 20 ); head.next.next = newNode( 15 ); head.next.next.next = newNode( 4 ); head.next.next.next.next = newNode( 10 ); // Create a loop for testing head.next.next.next.next.next = head.next.next; Node res = detectAndRemoveLoop(head); if (res == null ) System.out.print( "Loop does not exist" ); else System.out.print( "Loop starting node is " + res.key); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program to return first node of loop. class Node: def __init__( self , key): self .key = key self . next = None def newNode(key): temp = Node(key) return temp # 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 and remove loop # in a linked list that may contain loop def detectAndRemoveLoop(head): # If list is empty or has only one node # without loop if (head = = None or head. next = = None ): return None slow = head fast = head # Move slow and fast 1 and 2 steps # ahead respectively. slow = slow. next fast = fast. next . next # Search for loop using slow and # fast pointers while (fast and fast. next ): if (slow = = fast): break slow = slow. next fast = fast. next . next # If loop does not exist if (slow ! = fast): return None # If loop exists. Start slow from # head and fast from meeting point. slow = head while (slow ! = fast): slow = slow. next fast = fast. next return slow # Driver code if __name__ = = '__main__' : head = newNode( 50 ) head. next = newNode( 20 ) head. next . next = newNode( 15 ) head. next . next . next = newNode( 4 ) head. next . next . next . next = newNode( 10 ) # Create a loop for testing head. next . next . next . next . next = head. next . next res = detectAndRemoveLoop(head) if (res = = None ): print ( "Loop does not exist" ) else : print ( "Loop starting node is " + str (res.key)) # This code is contributed by rutvik_56 |
C#
// C# program to return // first node of loop. using System; class GFG{ 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 and remove loop // in a linked list that may contain loop static Node detectAndRemoveLoop(Node head) { // If list is empty or has // only one node without loop if (head == null || head.next == null ) return null ; Node slow = head, fast = head; // Move slow and fast 1 // and 2 steps ahead // respectively. slow = slow.next; fast = fast.next.next; // Search for loop using // slow and fast pointers while (fast != null && fast.next != null ) { if (slow == fast) break ; slow = slow.next; fast = fast.next.next; } // If loop does not exist if (slow != fast) return null ; // If loop exists. Start slow from // head and fast from meeting point. slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } // Driver code public static void Main(String[] args) { Node head = newNode(50); head.next = newNode(20); head.next.next = newNode(15); head.next.next.next = newNode(4); head.next.next.next.next = newNode(10); // Create a loop for testing head.next.next.next.next.next = head.next.next; Node res = detectAndRemoveLoop(head); if (res == null ) Console.Write( "Loop does not exist" ); else Console.Write( "Loop starting node is " + res.key); } } // This code is contributed by shikhasingrajput |
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 and remove loop // in a linked list that may contain loop function detectAndRemoveLoop(head) { // If list is empty or has // only one node without loop if (head == null || head.next == null ) return null ; let slow = head, fast = head; // Move slow and fast 1 // and 2 steps ahead // respectively. slow = slow.next; fast = fast.next.next; // Search for loop using // slow and fast pointers while (fast != null && fast.next != null ) { if (slow == fast) break ; slow = slow.next; fast = fast.next.next; } // If loop does not exist if (slow != fast) return null ; // If loop exists. Start slow from // head and fast from meeting point. slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } // Driver code let head = new Node(50); head.next = new Node(20); head.next.next = new Node(15); head.next.next.next = new Node(4); head.next.next.next.next = new Node(10); // Create a loop for testing head.next.next.next.next.next = head.next.next; let res = detectAndRemoveLoop(head); if (res == null ) document.write( "Loop does not exist" ); else document.write( "Loop starting node is " + res.key); // This code is contributed by unknown2108 </script> |
输出：
Loop starting node is 15
这种方法是如何工作的？ 在Floyd的循环查找算法之后，让慢速和快速在某个点相遇。下图显示了找到循环时的情况。
从上图我们可以得出如下结论
Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer)(m + n*x + k) = 2*(m + n*y + k)Note that before meeting the point shown above, fastwas moving at twice speed.x --> Number of complete cyclic rounds made by fast pointer before they meet first timey --> Number of complete cyclic rounds made by slow pointer before they meet first time
从上面的等式，我们可以得出如下结论
m + k = (x-2y)*nWhich means m+k is a multiple of n.
所以如果我们在同一时刻再次移动两个指针 同样的速度 这样一个指针（比如慢）从链表的头节点开始，其他指针（比如快）从集合点开始。当慢指针到达循环的开始（已经移动了m步）时，快指针也会移动m步，因为它们现在以相同的速度移动。因为m+k是n的倍数，从k开始，它们会在一开始相遇。他们以前也能见面吗？否，因为慢指针在m步之后第一次进入循环。
方法2： 在此方法中，将创建一个临时节点。被遍历的每个节点的下一个指针都指向这个临时节点。通过这种方式，我们使用节点的下一个指针作为标志来指示节点是否已被遍历。检查每个节点，看下一个节点是否指向临时节点。对于循环的第一个节点，我们第二次遍历它时，这个条件将为真，因此我们返回该节点。 代码以O（n）时间复杂度运行，并使用恒定的内存空间。
以下是上述方法的实施情况：
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 Node* 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 NULL; } // Check if next is already // pointing to temp if (head->next == temp) { break ; } // 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 head; } /* Driver program to test above function*/ int main() { Node* head = newNode(50); head->next = newNode(20); head->next->next = newNode(15); head->next->next->next = newNode(4); head->next->next->next->next = newNode(10); /* Create a loop for testing */ head->next->next->next->next->next = head->next->next; Node* res = detectLoop(head); if (res == NULL) cout << "Loop does not exist" ; else cout << "Loop starting node is " << res->key; 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(); } // Function to detect first node of loop // in a linked list that may contain loop static Node 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 null ; } // Check if next is already // pointing to temp if (head.next == temp) { break ; } // 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 head; } /* Driver program to test above function*/ public static void main(String[] args) { Node head = newNode( 50 ); head.next = newNode( 20 ); head.next.next = newNode( 15 ); head.next.next.next = newNode( 4 ); head.next.next.next.next = newNode( 10 ); /* Create a loop for testing */ head.next.next.next.next.next = head.next.next; Node res = detectLoop(head); if (res == null ) System.out.print( "Loop does not exist" ); else System.out.print( "Loop starting node is " + res.key); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program to return first node of loop class Node: def __init__( self , x): self .key = x self . next = None # A utility function to print a linked list def printList(head): while (head ! = None ): print (head.key, end = " " ) head = head. next # Function to detect first node of loop # in a linked list that may contain loop def detectLoop(head): # Create a temporary node temp = Node( - 1 ) while (head ! = None ): # This condition is for the case # when there is no loop if (head. next = = None ): return None # Check if next is already # pointing to temp if (head. next = = temp): break # Store the pointer to the next node # in order to get to it in the next step nex = head. next # Make next point to temp head. next = temp # Get to the next node in the list head = nex return head # Driver code if __name__ = = '__main__' : head = Node( 50 ) head. next = Node( 20 ) head. next . next = Node( 15 ) head. next . next . next = Node( 4 ) head. next . next . next . next = Node( 10 ) # Create a loop for testing head. next . next . next . next . next = head. next . next res = detectLoop(head) if (res = = None ): print ( "Loop does not exist" ) else : print ( "Loop starting node is " , res.key) # This code is contributed by mohit kumar 29 |
C#
// C# program to return first node of loop using System; class GFG{ 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 Node 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 null ; } // Check if next is already // pointing to temp if (head.next == temp) { break ; } // 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 head; } // Driver code public static void Main(String[] args) { Node head = newNode(50); head.next = newNode(20); head.next.next = newNode(15); head.next.next.next = newNode(4); head.next.next.next.next = newNode(10); // Create a loop for testing head.next.next.next.next.next = head.next.next; Node res = detectLoop(head); if (res == null ) Console.Write( "Loop does not exist" ); else Console.Write( "Loop starting node is " + res.key); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // javascript program to return first node of loop class Node { constructor() { this .key = 0; this .next = null ; } } function newNode(key) { temp = new Node(); temp.key = key; temp.next = null ; 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/>" ); } // Function to detect first node of loop // in a linked list that may contain loop function detectLoop( head) { // Create a temporary node temp = new Node(); while (head != null ) { // This condition is for the case // when there is no loop if (head.next == null ) { return null ; } // Check if next is already // pointing to temp if (head.next == temp) { break ; } // Store the pointer to the next node // in order to get to it in the next step nex = head.next; // Make next point to temp head.next = temp; // Get to the next node in the list head = nex; } return head; } /* Driver program to test above function */ head = newNode(50); head.next = newNode(20); head.next.next = newNode(15); head.next.next.next = newNode(4); head.next.next.next.next = newNode(10); /* Create a loop for testing */ head.next.next.next.next.next = head.next.next; res = detectLoop(head); if (res == null ) document.write( "Loop does not exist" ); else document.write( "Loop starting node is " + res.key); // This code contributed by gauravrajput1 </script> |
输出：
Loop starting node is 15
方法3： 我们也可以使用 散列 以检测循环的第一个节点。这个想法很简单，只需迭代整个链表，并将节点地址存储在一个集合中( C++ STL )逐个地，在将节点地址添加到集合中时，检查它是否已经包含该特定节点地址，如果没有，则添加要设置的节点地址。如果它已经存在于集合中，则当前节点是循环的第一个节点。
C++14
// The below function take head of Linked List as // input and return Address of first node in // the loop if present else return NULL. /* Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };*/ ListNode* detectCycle(ListNode* A) { // declaring map to store node address unordered_set<ListNode*> uset; ListNode *ptr = A; // Default consider that no cycle is present while (ptr != NULL) { // checking if address is already present in map if (uset.find(ptr) != uset.end()) return ptr; // if address not present then insert into the set else uset.insert(ptr); ptr = ptr->next; } return NULL; } // This code is contributed by Pankaj_Joshi |
JAVA
// The below function take head of Linked List as // input and return Address of first node in // the loop if present else return NULL. import java.io.*; import java.util.*; class GFG { static Node detectCycle(Node A) { // declaring map to store node address Set<Node> uset = new HashSet<Node>(); Node = A; // Default consider that no cycle is present while (ptr != NULL) { // checking if address is already present in map if (uset.contains(ptr)) { return ptr; } // if address not present then insert into the set else { uset.add(ptr); } ptr = ptr.next; } return null ; } } // This code is contributed by avanitrachhadiya2155 |
Python3
# The below function take head of Linked List as # input and return Address of first node in # the loop if present else return NULL. ''' Definition for singly-linked list. * class ListNode: * def __init__(self, x): * self.val=x * self.next=None * ''' def detectCycle(A): # Declaring map to store node # address uset = set () ptr = A # Default consider that no cycle # is present while (ptr ! = None ): # Checking if address is already # present in map if (ptr in uset): return ptr # If address not present then # insert into the set else : uset.add(ptr) ptr = ptr. next return None # This code is contributed by pratham76 |
C#
// The below function take head of Linked List as // input and return Address of first node in // the loop if present else return NULL. using System.Collections.Generic; public class GFG { class Node { public int key; public Node next; }; static Node detectCycle(Node A) { // declaring map to store node address HashSet<Node> uset = new HashSet<Node>(); Node ptr = A; // Default consider that no cycle is present while (ptr != null ) { // checking if address is already present in map if (uset.Contains(ptr)) { return ptr; } // if address not present then insert into the set else { uset.Add(ptr); } ptr = ptr.next; } return null ; } } // This code is contributed by 29AjayKumar |
Javascript
<script> // The below function take head of Linked List as // input and return Address of first node in // the loop if present else return NULL. function detectCycle(A) { // declaring map to store node address let uset = new Set(); let ptr = A; // Default consider that no cycle is present while (ptr != NULL) { // checking if address is already present in map if (uset.has(ptr)) { return ptr; } // if address not present then insert into the set else { uset.add(ptr); } ptr = ptr.next; } return null ; } // This code is contributed by patel2127 </script> |
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
