写一个函数 detectAndRemoveLoop（） 检查给定链表是否包含循环，如果存在循环，则删除循环并返回true。如果列表不包含循环，则返回false。下图显示了一个带有循环的链表。 detectAndRemoveLoop（） 必须将下面的列表更改为1->2->3->4->5->NULL。
null
![图片[1]-检测并删除链接列表中的循环-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/2009/04/Linked-List-Loop.gif)
我们还建议阅读以下帖子，作为这里讨论的解决方案的先决条件。 编写一个C函数来检测链表中的循环 在尝试移除循环之前，我们必须检测到它。上述文章中讨论的技术可以用于检测循环。要删除循环，我们需要做的就是获取指向循环最后一个节点的指针。例如，上图中值为5的节点。一旦我们有了指向最后一个节点的指针，我们就可以将这个节点的下一个设为NULL，循环就消失了。 我们可以很容易地使用散列或访问节点技术（在上面提到的帖子中讨论）来获取指向最后一个节点的指针。想法很简单：下一个已经被访问（或散列）的第一个节点就是最后一个节点。 我们也可以使用 弗洛伊德循环检测 检测并移除循环的算法。在弗洛伊德算法中，慢指针和快指针在循环节点处相遇。我们可以使用这个循环节点来删除循环。当Floyd算法用于循环检测时，有以下两种不同的消除循环的方法。
方法1（逐个检查） 我们知道，当快指针和慢指针在一个公共点相遇时，弗洛伊德的循环检测算法终止。我们还知道，这个公共点是一个循环节点（上图中的2或3或4或5）。将其地址存储在指针变量ptr2中。之后，从链表的开头开始，逐个检查节点是否可以从ptr2访问。每当我们找到一个可到达的节点时，我们就知道这个节点是链表中循环的起始节点，我们可以得到指向这个节点前一个节点的指针。
输出：
Linked List after removing loop 50 20 15 4 10
方法2（更好的解决方案）
- 该方法还依赖于Floyd的循环检测算法。
- 使用Floyd的循环检测算法检测循环，并获取指向循环节点的指针。
- 计算循环中的节点数。让伯爵来吧。
- 将一个指针固定到头部，将另一个指针固定到头部的第k个节点。
- 以相同的速度移动两个指针，它们将在循环开始节点处相遇。
- 获取指向循环最后一个节点的指针，并将其下一个设为NULL。
感谢WGPSASHANK推荐这种方法。 下图是代码中“删除循环”功能的试运行：
![图片[2]-检测并删除链接列表中的循环-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20190624/geeks_RemoveLoopInLinkedList.png)
以下是上述方法的实施情况：
C++
#include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to remove loop. */ void removeLoop( struct Node*, struct Node*); /* This function detects and removes loop in the list If loop was there in the list then it returns 1, otherwise returns 0 */ int detectAndRemoveLoop( struct Node* list) { struct Node *slow_p = list, *fast_p = list; // Iterate and find if loop exists or not while (slow_p && fast_p && fast_p->next) { slow_p = slow_p->next; fast_p = fast_p->next->next; /* If slow_p and fast_p meet at some point then there is a loop */ if (slow_p == fast_p) { removeLoop(slow_p, list); /* Return 1 to indicate that loop is found */ return 1; } } /* Return 0 to indicate that there is no loop*/ return 0; } /* Function to remove loop. loop_node --> Pointer to one of the loop nodes head --> Pointer to the start node of the linked list */ void removeLoop( struct Node* loop_node, struct Node* head) { struct Node* ptr1 = loop_node; struct Node* ptr2 = loop_node; // Count the number of nodes in loop unsigned int k = 1, i; while (ptr1->next != ptr2) { ptr1 = ptr1->next; k++; } // Fix one pointer to head ptr1 = head; // And the other pointer to k nodes after head ptr2 = head; for (i = 0; i < k; i++) ptr2 = ptr2->next; /* Move both pointers at the same pace, they will meet at loop starting node */ while (ptr2 != ptr1) { ptr1 = ptr1->next; ptr2 = ptr2->next; } // Get pointer to the last node while (ptr2->next != ptr1) ptr2 = ptr2->next; /* Set the next node of the loop ending node to fix the loop */ ptr2->next = NULL; } /* Function to print linked list */ void printList( struct Node* node) { // Print the list after loop removal while (node != NULL) { cout << node->data << " " ; node = node->next; } } struct Node* newNode( int key) { struct Node* temp = new Node(); temp->data = key; temp->next = NULL; return temp; } // Driver Code int main() { struct 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; detectAndRemoveLoop(head); cout << "Linked List after removing loop " ; printList(head); return 0; } // This code has been contributed by Striver |
C
#include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to remove loop. */ void removeLoop( struct Node*, struct Node*); /* This function detects and removes loop in the list If loop was there in the list then it returns 1, otherwise returns 0 */ int detectAndRemoveLoop( struct Node* list) { struct Node *slow_p = list, *fast_p = list; // Iterate and find if loop exists or not while (slow_p && fast_p && fast_p->next) { slow_p = slow_p->next; fast_p = fast_p->next->next; /* If slow_p and fast_p meet at some point then there is a loop */ if (slow_p == fast_p) { removeLoop(slow_p, list); /* Return 1 to indicate that loop is found */ return 1; } } /* Return 0 to indicate that there is no loop*/ return 0; } /* Function to remove loop. loop_node --> Pointer to one of the loop nodes head --> Pointer to the start node of the linked list */ void removeLoop( struct Node* loop_node, struct Node* head) { struct Node* ptr1 = loop_node; struct Node* ptr2 = loop_node; // Count the number of nodes in loop unsigned int k = 1, i; while (ptr1->next != ptr2) { ptr1 = ptr1->next; k++; } // Fix one pointer to head ptr1 = head; // And the other pointer to k nodes after head ptr2 = head; for (i = 0; i < k; i++) ptr2 = ptr2->next; /* Move both pointers at the same pace, they will meet at loop starting node */ while (ptr2 != ptr1) { ptr1 = ptr1->next; ptr2 = ptr2->next; } // Get pointer to the last node while (ptr2->next != ptr1) ptr2 = ptr2->next; /* Set the next node of the loop ending node to fix the loop */ ptr2->next = NULL; } /* Function to print linked list */ void printList( struct Node* node) { // Print the list after loop removal while (node != NULL) { cout << node->data << " " ; node = node->next; } } struct Node* newNode( int key) { struct Node* temp = new Node(); temp->data = key; temp->next = NULL; return temp; } // Driver Code int main() { struct 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; detectAndRemoveLoop(head); cout << "Linked List after removing loop " ; printList(head); return 0; } // This code has been contributed by Striver |
JAVA
// Java program to detect and remove loop in linked list class LinkedList { static Node head; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } // Function that detects loop in the list int detectAndRemoveLoop(Node node) { Node slow = node, fast = node; while (slow != null && fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; // If slow and fast meet at same point then loop is present if (slow == fast) { removeLoop(slow, node); return 1 ; } } return 0 ; } // Function to remove loop void removeLoop(Node loop, Node head) { Node ptr1 = loop; Node ptr2 = loop; // Count the number of nodes in loop int k = 1 , i; while (ptr1.next != ptr2) { ptr1 = ptr1.next; k++; } // Fix one pointer to head ptr1 = head; // And the other pointer to k nodes after head ptr2 = head; for (i = 0 ; i < k; i++) { ptr2 = ptr2.next; } /* Move both pointers at the same pace, they will meet at loop starting node */ while (ptr2 != ptr1) { ptr1 = ptr1.next; ptr2 = ptr2.next; } // Get pointer to the last node while (ptr2.next != ptr1) { ptr2 = ptr2.next; } /* Set the next node of the loop ending node to fix the loop */ ptr2.next = null ; } // Function to print the linked list void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } // Driver program to test above functions public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node( 50 ); list.head.next = new Node( 20 ); list.head.next.next = new Node( 15 ); list.head.next.next.next = new Node( 4 ); list.head.next.next.next.next = new Node( 10 ); // Creating a loop for testing head.next.next.next.next.next = head.next.next; list.detectAndRemoveLoop(head); System.out.println( "Linked List after removing loop : " ); list.printList(head); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python program to detect and remove loop in 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 def detectAndRemoveLoop( self ): slow_p = 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 and fast_p meet at some point then # there is a loop if slow_p = = fast_p: self .removeLoop(slow_p) # Return 1 to indicate that loop is found return 1 # Return 0 to indicate that there is no loop return 0 # Function to remove loop # loop_node --> pointer to one of the loop nodes # head --> Pointer to the start node of the linked list def removeLoop( self , loop_node): ptr1 = loop_node ptr2 = loop_node # Count the number of nodes in loop k = 1 while (ptr1. next ! = ptr2): ptr1 = ptr1. next k + = 1 # Fix one pointer to head ptr1 = self .head # And the other pointer to k nodes after head ptr2 = self .head for i in range (k): ptr2 = ptr2. next # Move both pointers at the same place # they will meet at loop starting node while (ptr2 ! = ptr1): ptr1 = ptr1. next ptr2 = ptr2. next # Get pointer to the last node while (ptr2. next ! = ptr1): ptr2 = ptr2. next # Set the next node of the loop ending node # to fix the loop ptr2. next = 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 the LinkedList def printList( self ): temp = self .head while (temp): print (temp.data, end = ' ' ) temp = temp. next # Driver program llist = LinkedList() llist.push( 10 ) llist.push( 4 ) llist.push( 15 ) llist.push( 20 ) llist.push( 50 ) # Create a loop for testing llist.head. next . next . next . next . next = llist.head. next . next llist.detectAndRemoveLoop() print ( "Linked List after removing loop" ) llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// A C# program to detect and remove loop in linked list using System; public class LinkedList { Node head; public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } // Function that detects loop in the list int detectAndRemoveLoop(Node node) { Node slow = node, fast = node; while (slow != null && fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; // If slow and fast meet at same // point then loop is present if (slow == fast) { removeLoop(slow, node); return 1; } } return 0; } // Function to remove loop void removeLoop(Node loop, Node head) { Node ptr1 = loop; Node ptr2 = loop; // Count the number of nodes in loop int k = 1, i; while (ptr1.next != ptr2) { ptr1 = ptr1.next; k++; } // Fix one pointer to head ptr1 = head; // And the other pointer to k nodes after head ptr2 = head; for (i = 0; i < k; i++) { ptr2 = ptr2.next; } /* Move both pointers at the same pace, they will meet at loop starting node */ while (ptr2 != ptr1) { ptr1 = ptr1.next; ptr2 = ptr2.next; } // Get pointer to the last node while (ptr2.next != ptr1) { ptr2 = ptr2.next; } /* Set the next node of the loop ending node to fix the loop */ ptr2.next = null ; } // Function to print the linked list void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } // Driver program to test above functions public static void Main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(50); list.head.next = new Node(20); list.head.next.next = new Node(15); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(10); // Creating a loop for testing list.head.next.next.next.next.next = list.head.next.next; list.detectAndRemoveLoop(list.head); Console.WriteLine( "Linked List after removing loop : " ); list.printList(list.head); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to detect and // remove loop in linked list var head; class Node { constructor(val) { this .data = val; this .next = null ; } } // Function that detects loop in the list function detectAndRemoveLoop(node) { var slow = node, fast = node; while (slow != null && fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; // If slow and fast meet at same // point then loop is present if (slow == fast) { removeLoop(slow, node); return 1; } } return 0; } // Function to remove loop function removeLoop(loop, head) { var ptr1 = loop; var ptr2 = loop; // Count the number of nodes in loop var k = 1, i; while (ptr1.next != ptr2) { ptr1 = ptr1.next; k++; } // Fix one pointer to head ptr1 = head; // And the other pointer to // k nodes after head ptr2 = head; for (i = 0; i < k; i++) { ptr2 = ptr2.next; } /* Move both pointers at the same pace, they will meet at loop starting node */ while (ptr2 != ptr1) { ptr1 = ptr1.next; ptr2 = ptr2.next; } // Get pointer to the last node while (ptr2.next != ptr1) { ptr2 = ptr2.next; } /* Set the next node of the loop ending node to fix the loop */ ptr2.next = null ; } // Function to print the linked list function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } // Driver code 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); // Creating a loop for testing head.next.next.next.next.next = head.next.next; detectAndRemoveLoop(head); document.write( "Linked List after removing loop : " ); printList(head); // This code is contributed by todaysgaurav </script> |
输出：
Linked List after removing loop 50 20 15 4 10
方法3（优化方法2：不计算循环中的节点） 我们不需要计算循环中的节点数。在检测到循环后，如果我们从头部启动慢指针，并以相同的速度移动慢指针和快指针，直到快指针不相交，它们将在循环开始时相交。
这是怎么回事？ 在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. Thus we can write, m + k = i*n or m = i*n - k.Hence, distance moved by slow pointer: m, is equal to distance moved by fast pointer:i*n - k or (i-1)*n + n - k (cover the loop completely i-1 times and start from n-k).
所以如果我们再次开始移动两个指针 同样的速度 这样一个指针（比如慢）从链表的头节点开始，另一个指针（比如快）从集合点开始。当慢指针到达循环的开始（已经移动了m步）时，快指针也会移动m步，因为它们现在以相同的速度移动。因为m+k是n的倍数，从k开始，它们会在一开始相遇。他们以前也能见面吗？否，因为慢指针在m步之后第一次进入循环。
C++
// C++ program to detect and remove 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 void detectAndRemoveLoop(Node* head) { // If list is empty or has only one node // without loop if (head == NULL || head->next == NULL) return ; 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 exists */ if (slow == fast) { slow = head; // this check is needed when slow // and fast both meet at the head of the LL // eg: 1->2->3->4->5 and then // 5->next = 1 i.e the head of the LL if (slow == fast) { while (fast->next != slow) fast = fast->next; } else { while (slow->next != fast->next) { slow = slow->next; fast = fast->next; } } /* since fast->next is the looping point */ fast->next = NULL; /* remove loop */ } } /* Driver program to test above function*/ int main() { Node* head = newNode(50); head->next = head; 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; detectAndRemoveLoop(head); printf ( "Linked List after removing loop " ); printList(head); return 0; } |
JAVA
// Java program to detect // and remove loop in linked list class LinkedList { static Node head; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } // Function that detects loop in the list void detectAndRemoveLoop(Node node) { // If list is empty or has only one node // without loop if (node == null || node.next == null ) return ; Node slow = node, fast = node; // 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 exists */ if (slow == fast) { slow = node; if (slow != fast) { while (slow.next != fast.next) { slow = slow.next; fast = fast.next; } /* since fast->next is the looping point */ fast.next = null ; /* remove loop */ } /* This case is added if fast and slow pointer meet at first position. */ else { while (fast.next != slow) { fast = fast.next; } fast.next = null ; } } } // Function to print the linked list void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } // Driver code public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node( 50 ); list.head.next = new Node( 20 ); list.head.next.next = new Node( 15 ); list.head.next.next.next = new Node( 4 ); list.head.next.next.next.next = new Node( 10 ); // Creating a loop for testing head.next.next.next.next.next = head.next.next; list.detectAndRemoveLoop(head); System.out.println( "Linked List after removing loop : " ); list.printList(head); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python program to detect and remove loop # 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 def detectAndRemoveLoop( self ): if self .head is None : return if self .head. next is None : return 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 and fast_p meet at some point then # there is a loop if slow_p = = fast_p: slow_p = self .head # Finding the beginning of the loop while (slow_p. next ! = fast_p. next ): slow_p = slow_p. next fast_p = fast_p. next # Sinc fast.next is the looping point fast_p. next = None # Remove loop # Utility function to print the LinkedList def printList( self ): temp = self .head while (temp): print (temp.data, end = ' ' ) temp = temp. next # Driver program llist = LinkedList() llist.head = Node( 50 ) llist.head. next = Node( 20 ) llist.head. next . next = Node( 15 ) llist.head. next . next . next = Node( 4 ) llist.head. next . next . next . next = Node( 10 ) # Create a loop for testing llist.head. next . next . next . next . next = llist.head. next . next llist.detectAndRemoveLoop() print ( "Linked List after removing loop" ) llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to detect and remove loop in linked list using System; public class LinkedList { public Node head; public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } // Function that detects loop in the list void detectAndRemoveLoop(Node node) { // If list is empty or has only one node // without loop if (node == null || node.next == null ) return ; Node slow = node, fast = node; // 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 exists */ if (slow == fast) { slow = node; while (slow.next != fast.next) { slow = slow.next; fast = fast.next; } /* since fast->next is the looping point */ fast.next = null ; /* remove loop */ } } // Function to print the linked list void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } // Driver program to test above functions public static void Main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(50); list.head.next = new Node(20); list.head.next.next = new Node(15); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(10); // Creating a loop for testing list.head.next.next.next.next.next = list.head.next.next; list.detectAndRemoveLoop(list.head); Console.WriteLine( "Linked List after removing loop : " ); list.printList(list.head); } } // This code contributed by Rajput-Ji |
Javascript
<script> // javascript program to detect // and remove loop in linked list var head; class Node { constructor(val) { this .data = val; this .next = null ; } } // Function that detects loop in the list function detectAndRemoveLoop(node) { // If list is empty or has only one node // without loop if (node == null || node.next == null ) return ; var slow = node, fast = node; // 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 exists */ if (slow == fast) { slow = node; if (slow != fast) { while (slow.next != fast.next) { slow = slow.next; fast = fast.next; } /* since fast->next is the looping point */ fast.next = null ; /* remove loop */ } /* This case is added if fast and slow pointer meet at first position. */ else { while (fast.next != slow) { fast = fast.next; } fast.next = null ; } } } // Function to print the linked list function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } // Driver code 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); // Creating a loop for testing head.next.next.next.next.next = head.next.next; detectAndRemoveLoop(head); document.write( "Linked List after removing loop : " ); printList(head); // This code is contributed by umadevi9616 </script> |
输出：
Linked List after removing loop 50 20 15 4 10
方法4哈希：哈希链表节点的地址 我们可以散列无序映射中链表节点的地址，只需检查映射中是否已经存在该元素。如果它存在，我们已经到达一个已经存在一个循环的节点，因此我们需要使最后一个节点的下一个指针为空。
C++
// C++ program to detect and remove 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 void hashAndRemove(Node* head) { // hash map to hash addresses of the linked list nodes unordered_map<Node*, int > node_map; // pointer to last node Node* last = NULL; while (head != NULL) { // if node not present in the map, insert it in the map if (node_map.find(head) == node_map.end()) { node_map[head]++; last = head; head = head->next; } // if present, it is a cycle, make the last node's next pointer NULL else { last->next = NULL; break ; } } } /* Driver program to test above function*/ int main() { Node* head = newNode(50); head->next = head; 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; // printList(head); hashAndRemove(head); printf ( "Linked List after removing loop " ); printList(head); return 0; } |
JAVA
// Java program to detect and remove 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; } // Function to print the linked list void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } // Returns true if the loop is removed from the linked // list else returns false. static boolean removeLoop(Node h) { HashSet<Node> s = new HashSet<Node>(); Node prev = null ; while (h != null ) { // If we have already has this node // in hashmap it means their is a cycle and we // need to remove this cycle so set the next of // the previous pointer with null. if (s.contains(h)) { prev.next = null ; return true ; } // If we are seeing the node for // the first time, insert it in hash else { s.add(h); prev = 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 (removeLoop(head)) { System.out.println( "Linked List after removing loop" ); llist.printList(head); } else System.out.println( "No Loop found" ); } } // This code is contributed by Animesh Nag. |
C#
// C# program to detect and remove loop in a linked list using System; using System.Collections.Generic; public class LinkedList { public 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 ; } } // Function to print the linked list void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } // Returns true if the loop is removed from the linked // list else returns false. bool removeLoop(Node h) { HashSet<Node> s = new HashSet<Node>(); Node prev = null ; while (h != null ) { // If we have already has this node // in hashmap it means their is a cycle and we // need to remove this cycle so set the next of // the previous pointer with null. if (s.Contains(h)) { prev.next = null ; return true ; } // If we are seeing the node for // the first time, insert it in hash else { s.Add(h); prev = h; h = h.next; } } return false ; } /* Driver program to test above function */ public static void Main() { LinkedList list = new LinkedList(); list.head = new Node(50); list.head.next = new Node(20); list.head.next.next = new Node(15); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(10); /*Create loop for testing */ list.head.next.next.next.next.next = list.head.next.next; if (list.removeLoop(list.head)) { Console.WriteLine( "Linked List after removing loop" ); list.printList(list.head); } else Console.WriteLine( "No Loop found" ); } } // This code is contributed by ihritik |
Javascript
<script> // javascript program to detect and remove loop in a linked list class LinkedList { /* Linked list Node */ class Node { constructor(val) { this .data = val; this .next = null ; } } var head; // head of list /* 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; return head; } // Function to print the linked list function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } // Returns true if the loop is removed from the linked // list else returns false. function removeLoop(h) { var s = new Set(); var prev = null ; while (h != null ) { // If we have already has this node // in hashmap it means their is a cycle and we // need to remove this cycle so set the next of // the previous pointer with null. if (s.has(h)) { prev.next = null ; return true ; } // If we are seeing the node for // the first time, insert it in hash else { s.add(h); prev = h; h = h.next; } } return false ; } /* Driver program to test above function */ head = push(50); head.next = push(20); head.next.next=push(4); head.next.next.next=push(15); head.next.next.next.next=push(10); /* Create loop for testing */ head.next.next.next.next.next = head.next.next; if (removeLoop(head)) { document.write( "Linked List after removing loop<br/>" ); printList(head); } else document.write( "No Loop found" ); // This code is contributed by gauravrajput1 </script> |
输出
Linked List after removing loop 50 20 15 4 10
我们感谢Shubham Agrawal提出这一解决方案。
感谢Gaurav Ahirwar提出上述解决方案。 如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
